歐拉函數+容斥原理-HDU1695

https://vj.xtuacm.cf/contest/view.action?cid=57#problem/O

這題要轉換成求兩個區間内互斥的數 有多少對 并且不重複

題目大意：求1到b内x，1到d内y，gcd(x,y)= k 的對數，二進制組無序，要求不重複

x和y的最大公約數都是k，也就是說x，y都是k的倍數，b /= k , d /= k 得到新的區間，需要找到新區間的中互質的對數，要求不重複，是以使大的數為d ，小的數為b ，從1到b周遊–>i,計算1到d中與i互質的個數，累加得到最後的結果。

#include <cstdio>
#include <iostream>
#define ll long long
using namespace std;
int zhi[], cnt;

void fen(int n)
{
    cnt=;
    for(int i=;i*i<=n;i++)
    {
        if(n%i==)
        {
            zhi[cnt++]=i;
            while(n%i==)
                n=n/i;
        }
    }
    if(n>)
        zhi[cnt++]=n;
}
ll rongchi(int n)
{
    ll sum=;
    for(int i=;i<(<<cnt);i++)
    {
        int k=,l=;
        for(int j=;j<cnt;j++)
        {
            if(i&(<<j))
            {
                l=l*zhi[j];
                k++;
            }

        }
        if(k&)
            sum+=n/l;
        else
            sum-=n/l;
    }
    return (ll)n-sum;
}
int main()
{
    int t;
    scanf("%d",&t);
    for(int j=;j<=t;j++)
    {
        int a,b,c,d,k;
        scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
        if(k==)
            printf("Case %d: 0\n",j);
        else
        {
            b=b/k;d=d/k;
            if(b>d)swap(b,d);
            ll ans=;
            for(int i=;i<=b;i++)//j>=i
            {
                fen(i);
                ans+=(rongchi(d)-rongchi(i-));
                //計算從i到b相應的質數，并減去重複的,減去小于i的與d互質的個數，因為在前面計算的過程中已經計算過了那些小于i與d互質的數
            }
            printf("Case %d: %I64d\n",j,ans);
        }

    }
    return ;
}