UESTC 1720 无平方因数数（数论，容斥）

UESTC 1720 无平方因子数（数论，容斥）

转载请注明出处，谢谢http://blog.****.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 1000005
using 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;
}