题目大意

求出1～n中不能被“完全平方数”（不含1）整除的数的个数。

算法分析

一开始看到1e14 真是吓坏了，好怕mobius用不了，后来一细分析，其实题目还是很水的。
自己对莫比乌斯的模版题的理解相对深入，写出mobius下公式

Screen Shot 2016-06-26 at 7.26.10 PM.png

应该有新手不大熟悉这个公式，可以留言一起讨论，当时我学mobius真实难受，没人人帮忙都得靠自己一点一点试，不想这种事再让别人被坑了，或者加我qq 844704 加的时候说明下...

复杂度分析

mobius的结果打表就可以了，复杂度也就是O(n)多一点不到 O(n*ln(n))，最后那个结果那我偷懒了用的 O(n)其实可以分段求和，复杂会再度压缩。

AC代码

//
//  main.cpp
//  SQFREE - Square-free integers
//
//  Created by ccccsober on 6/26/16.
//  Copyright © 2016 cccsober. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <cassert>
#include <string>
#include <sstream>
#include <math.h>
#include <set>
#include <bitset>
#include <vector>
#include <stack>
#include <map>
#include <queue>
#include <deque>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cctype>
#include <complex>
using namespace std;
const int MAX1= (1e7)+3  ;
const double plus=0.49999999;
const int INF=0x3f3f3f3f;
typedef long long LL;
typedef unsigned long long ULL;
int  mobius[MAX1];
bool vis[MAX1];
vector<int> prime;
void Mobius(){
    memset(vis,0,sizeof(vis));
    mobius[1]=1;
    for(int i=2;i<MAX1;i++){
        if(!vis[i]){
            mobius[i]=-1;
            prime.push_back(i);
        }
        for(int j=0;j<prime.size()&&i*prime[j]<MAX1;j++){
            vis[i*prime[j]]=1;
            if(i%prime[j])
                mobius[i*prime[j]]=-mobius[i];
            else{
                mobius[i*prime[j]]=0;
                break;
            }
        }
    }
}
int main(int argc, const char * argv[]) {
    freopen("/Users/sperc4/Desktop/input.txt", "r", stdin);
    Mobius();
    int t;
    scanf("%d",&t);
    while(t--){
        LL n;
        LL ans=0;
        scanf("%lld",&n);
        int len=sqrt(n);
        for(int i=2;i<=len;i++)
            ans+=mobius[i]*n/i/i;
        cout<<n+ans<<endl;
    }
    fclose(stdin);
    //      fclose(stdout);
    return 0;
}