若(x,y)=k,则(x/k,y/k)=1.
在[1,b/k],[1,d/k]中找互质的点对即可。
对于1<=y<=b/k,则与y互质的x数量为φ(y).
对于y>b/k则要对y分解质因子,然后利用容斥原理找到与y不互质的x数量,再拿y相减即可。
#include <cstdio> #include <iostream> using namespace std; const int maxn=100000+5; int b,d; typedef long long LL; int ph[maxn],num[maxn],k,fac[maxn],cnt; void getph() { for(int i=1;i<maxn;i++) if(i%2==0) ph[i]=i/2; else ph[i]=i; k=0; num[k++]=2; for(int i=3;i<maxn;i+=2) if(ph[i]==i){ num[k++]=i; for(int j=i;j<maxn;j+=i) ph[j]=ph[j]/i*(i-1); } } int work() { int s=0; for(int i=1;i<(1<<cnt);i++) { int tmp=1,t=0; for(int j=0;j<cnt;j++) if((1<<j)&i){ t++; tmp*=fac[j]; } if(t%2) s+=b/tmp; else s-=b/tmp; } return b-s; } int main() { int T,kas=0; scanf("%d",&T); while(T--) { int a,c,K; scanf("%d%d%d%d%d",&a,&b,&c,&d,&K); printf("Case %d: ",++kas); if(K==0){ printf("0\n"); continue; } getph(); b/=K; d/=K; if(b>d) swap(b,d); LL ans=0; for(int i=1;i<=b;i++) ans+=ph[i]; for(int i=b+1;i<=d;i++) { cnt=0;a=i; for(int j=0;j<k&&num[j]*num[j]<=a;j++) if(a%num[j]==0){ fac[cnt++]=num[j]; while(a%num[j]==0) a/=num[j]; } if(a>1) fac[cnt++]=a; ans+=work(); } printf("%I64d\n",ans); } return 0; }