题目链接
mobius||容斥原理
题目大意
求出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;
}
