题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1695
题意:因为题目已经说明固定a=1,c=1,所以就是x在[1,b],y在[1,d],求有多少对(x,y)满足gcd(x,y)=k;(gcd指的是求俩数的最小公倍数)。
求解方式:一共有两种:一个是用容斥原理+欧拉函数,一个是莫比乌斯反演,在这我们用的是容器定理+欧拉函数,莫比乌斯反演我会另开一篇文章来讲。
先来说一下欧拉函数。欧拉函数用phi(n)表示(应该是φ(n),但φ的读音就是phi,在这就用phi表示φ),phi(n)表示小于n的数中有phi(n)个数与n互质。
欧拉函数通式:φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),
再来说一下容斥原理。公式:
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<string> #include<cmath> #include<vector> #include<map> #include<queue> using namespace std; long long a,b,c,d,k; /*素数筛选和合数分解*/ const int maxn=100100; int prime[maxn+1]; void getprime(){ memset(prime,0,sizeof(prime)); for(int i=2;i<maxn;i++){ if(!prime[i]) prime[++prime[0]]=i; for(int j=1;j<=prime[0]&&prime[j]<=maxn/i;j++){ prime[prime[j]*i]=1; if(i%prime[j]==0) break; } } } /*合数分解*/ long long factor[105][2]; int fatcnt; int getfactor(long long x){ if(x==0) return 0; fatcnt=0; long long tmp=x; for(int i=1;prime[i]<=tmp/prime[i];i++){ factor[fatcnt][1]=0; if(tmp%prime[i]==0){ factor[fatcnt][0]=prime[i]; while(tmp%prime[i]==0){ factor[fatcnt][1]++; tmp/=prime[i]; } fatcnt++; } } if(tmp!=1){ factor[fatcnt][0]=tmp; factor[fatcnt++][1]=1; } return fatcnt; } /*欧拉函数筛*/ int phi[100100]; void phitable_ZY(int n){ memset(phi,0,sizeof(phi)); phi[1]=1; for(int i=2;i<=n;i++) if(!phi[i]) for(int j=i;j<=n;j+=i){ if(!phi[j]) phi[j]=j; phi[j]=phi[j]/i*(i-1); } } long long cr(long long i){ getfactor(i); long long ans=0; for(int i=1;i<(1<<fatcnt);i++){ long long t=1; int cut=0; for(int j=0;j<fatcnt;j++){ if(i&(1<<j)) t*=factor[j][0],cut++; } if(cut&1) ans+=b/t; else ans-=b/t; } return (long long)b-ans; } int main(){ getprime(); phitable_ZY(100010); int t,cas=0; scanf("%I64d",&t); while(t--){ scanf("%I64d%I64d%I64d%I64d%I64d",&a,&b,&c,&d,&k); printf("Case %d: ",++cas); if(k==0||k>b||k>d){ printf("0\n"); continue; } b/=k; d/=k; long long ans=0; if(b>d) swap(b,d); for(int i=1;i<=b;i++) ans+=phi[i]; for(int i=b+1;i<=d;i++){ ans+=cr(i); } printf("%I64d\n",ans); } return 0; }
原文:http://blog.csdn.net/wangzhen_yu/article/details/44567179