UESTC 1720 无平方因子数（数论，容斥）
转载请注明出处，谢谢http://blog.csdn.net/acm_cxlove/article/details/7854526 by---cxlove
题目：无平方因子数即对于任意一个素数p，p^2都不会整除那个数，如1 , 5=5 , 15=3*5都是无平方因子数，而20=2^2*5不是。现在给定一个n (1 <= n < 10^12) ，求区间[1,n]中无平方因子数的个数。
http://acm.uestc.edu.cn/problem.php?pid=1720
水水一发~~~~囧
打出素数表，然后找出区间内有多少个数是有平方因子的。显然是容斥原理
之前用的是枚举的写法，总是TLE，怀疑自己容斥都不会写了， 囧。
之后又因为溢出，姿势不正确，TLE,WA也几次， 真心弱啊
#include<iostream>#include<cstdio>#include<cstring>#include<queue>#include<cmath>#include<string>#include<vector>#include<algorithm>#include<map>#include<set>#define maxn 200005#define eps 1e-8#define inf 1<<30#define LL long long#define zero(a) fabs(a)<eps#define MOD 19901014#define N 1000005using namespace std;bool flag[N]={0};int prime[N],cnt=0;void Prime(){for(int i=2;i<N;i++){if(flag[i]) continue;prime[cnt++]=i;for(int j=2;j*i<N;j++)flag[i*j]=true;}}LL n,ans;LL dfs(int idx,LL num){LL ret=0;for(int i=idx;i<cnt&&(LL)prime[i]*prime[i]<=num;i++)ret+=num/prime[i]/prime[i]-dfs(i+1,num/prime[i]/prime[i]);return ret;}int main(){Prime();int t;scanf("%d",&t);while(t--){scanf("%lld",&n);printf("%lld\n",n-dfs(0,n));}return 0;}