题意： 给了 a、b、c、d、k 五个数 求gcd(x,y)=k的对数 其中 a<=x<=b c<=y<=d 并且所有数据的 a和c都是1
gcd(x,y)=k -> gcd(x/k，y/k)=1 (1<=x<=b/k, 1<=y<=d/k) 也就是求互质的对数 那么 我们可以去枚举x的范围去算y中与x互质的个数 但为了避免重复的情况 比如1 3 和3 1算一对 那么我们就假定x<y 所以我们算的是大于x小于等于y并且与x互质的个数 我们可以用容斥原理算出大于x小于等于y的数中是x的质因数的倍数的个数sum 然后y-x-sum就是x与1~d/k中互质的对数 枚举所有的x即可
不会容斥原理请下转 https://blog.csdn.net/qq_43563669/article/details/98402274
#include<bits/stdc++.h> using namespace std; typedef long long ll; vector<ll>hsy[100005]; int main() { bool v[100005]= {0}; v[1]=v[0]=1; for(ll i=2; i<=100000; i++) if(!v[i]) { for(ll j=i; j<=100000; j+=i) { hsy[j].push_back(i); v[j]=1; } } int t; cin>>t; for(int w=1; w<=t; w++) { ll a,b,c,d,k; cin>>a>>b>>c>>d>>k; printf("Case %d: ",w); if(k==0 || k>b || k>d)///特判 puts("0"); else { b=b/k,d=d/k; if(b>d) swap(b,d); ll ans=d; for(int i=2; i<=b; i++)///枚举每一个b { ll len=hsy[i].size(),u=1<<len,s=0; for(ll j=1; j<u; j++)///二进制枚举 { ll m=1,num=0; for(ll k=0; k<len; k++)///对每一个二进制数进行移位判断1的个数 { if((j>>k)&1) { m=m*hsy[i][k];///计算倍数 num++; } } ///下面的i felse是计算大于i小于等于d的数中是m的倍数的个数 if(num&1)///奇加 s=s+d/m-i/m; else///偶减 s=s-d/m+i/m; } ans=ans+d-i-s; } cout<<ans<<endl; } } }