转载请注明出处,谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents
by---cxlove
题目:N*M的格点上有树,从0,0点可以看到多少棵树。
发现如果A1/B1=A2/B2那么就有一棵树看不到,所以就是找出Ai/Bi有多少种。
再可以发现A/B中,如果A,B有大于1的公约数,则A=A'*D B=B'*D,那么A/B=A'/B',也就是存在另外一组数和这种相等,则问题转换成有多少对互质的数,枚举i,从1-M中找与i互质的数,其中1<=i<=N。
容斥原理,先预处理i的所有素因子,然后容斥求就可以了。
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<vector> #include<string> #include<algorithm> #include<queue> #define LL long long #define eps 1e-7 using namespace std; int prime[100005][20]; int cnt[100005]={0}; //筛选法求出所有素因子 void Init(){ for(int i=2;i<=100000;i++){ if(cnt[i]) continue; prime[i][0]=i; cnt[i]=1; for(int j=2;j*i<=100000;j++) prime[i*j][cnt[i*j]++]=i; } } LL dfs(int m,int n,int idx){ LL ret=0; for(int i=idx;i<cnt[m];i++) ret+=n/prime[m][i]-dfs(m,n/prime[m][i],i+1); return ret; } int main(){ Init(); int t,n,m; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&m); //当i为1的时候肯定为n LL ans=n; for(int i=2;i<=m;i++) ans+=n-dfs(i,n,0); printf("%I64d\n",ans); } return 0; }