hdu 1695 GCD 容斥 欧拉函数预处理

题意：求x在1-b里， y在1-d里，有多少对x，y使得gcd(x, y)==k

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1695

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn=100010;

int phi[maxn];
vector<int> v[maxn];

void init()
{
    memset(phi,0,sizeof(phi));
    phi[1]=1;
    for(int i=2; i<=100000; i++)
        if(!phi[i])
        {
            for(int j=i; j<=100000; j+=i)
            {
                if(!phi[j])  phi[j]=j;
                phi[j]=phi[j]/i*(i-1);

            }
        }
}

void init1()
{

    for(int i=2; i<=100000; i++)
    {
        int num=i;
        for(int j=2; j*j<=num; j++)
        {
            if(num%j==0)
            {
                v[i].push_back(j);
                while(num%j==0) num/=j;
            }
        }
        if(num>1) v[i].push_back(num);
    }
}

ll solve(int l,int r)
{
    ll ans=0;
    for(int i=l+1; i<=r; i++)
    {
        int ret=0;
        for(int j=1; j<(1<<v[i].size()); j++)
        {
            int cnt=0,val=1;
            for(int k=0; k<(int)v[i].size(); k++)
            {
                if(j&(1<<k))
                {
                    cnt++;
                    val*=v[i][k];
                }
            }
            if(cnt&1) ret+=l/val;//从1到L有多少个val
            else ret-=l/val;
        }
        ans=ans+l-ret;
    }
    return ans;
}

int main(void)
{
    init();//计算phi(1)到phi[maxn]的每一个phi函数值
    init1();//计算1到maxn每一个数的素因子  //这两项初始化应该是预处理，随着maxn的变大，时间上很有压力
    int t;
    scanf("%d",&t);
    for(int kase=1; kase<=t; kase++)
    {
        printf("Case %d: ",kase);
        int a,b,c,d,k;
        scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
        if(k==0)
        {
            printf("0\n");    //k==0时，最大公约数会等于0的对数也就只有0对
            continue;
        }
        b/=k,d/=k;
        if(b>d)
        {
            int t=b;
            b=d;
            d=t;
        }//保证b<d;
        ll ans=0;
        for(int i=1; i<=b; i++) ans+=phi[i]; //这里需要注意的是，如果这里取了等于号，表示算了phi[b],那么solve()i必须等于l+1,这里不去等，那么i取l
        ans+=solve(b,d);//对于这个区间的任意一个num，求1到b之间有多少个是与num互质的
        printf("%I64d\n",ans);
    }
    return 0;
}