hdu 1695(容斥原理)

题意：
给了 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;
        }
    }
}