HDU 1695 GCD

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

题意:求满足x属于[1,b]和y属于[1,d]的gcd(x,y)=k的数量,其中(x,y)==(y,x)算一种
思路:求gcd(i,j)=k的小小变形,用莫比乌斯反演算出所有对数后减去calc(min(b,d),min(b,d),k)的数量除2即可。

#include <bits/stdc++.h>
using namespace std;
typedef __int64 ll;
const int maxn=100000+5;
template<typename T>
inline T read(T&x){
    x=0;int _f=0;char ch=getchar();
    while(ch<'0'||ch>'9')_f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x=_f?-x:x;
}
bool isPrime[maxn];
int mu[maxn];
int primes[maxn];
int sum[maxn];
void sieve(){
    int num=0;
    fill(isPrime,isPrime+maxn,1);
    mu[1]=1;
    for (int i=2;i<maxn;i++){
        if (isPrime[i]){
            primes[num++]=i;
            mu[i]=-1;
        }
        static int d;
        for (int j=0;j<num && (d=i*primes[j])<maxn;j++){
            isPrime[d]=false;
            if (i%primes[j]==0){
                mu[d]=0;
                break;
            }
            else mu[d]=-mu[i];
        }
    }
    for (int i=1;i<maxn;i++) sum[i]+=sum[i-1]+mu[i];
}
ll calc(int n,int m,int d){
    if (n>m) swap(n,m);
    ll ans=0;
    n/=d,m/=d;
    for (int i=1,last=1;i<=n;i=last+1){
        last=min(n/(n/i),m/(m/i));
        ans+=(ll)(sum[last]-sum[i-1])*(n/i)*(m/i);
    }
    return ans;
}
int main(){
    int T;
    read(T);
    sieve();
    for (int cas=1;cas<=T;cas++){
        int a,b,c,d,k;
        read(a),read(b),read(c),read(d),read(k);
        printf("Case %d: ",cas);
        if (k==0){
            printf("0\n");
            continue;
        }
        if (b>d) swap(b,d);
        printf("%I64d\n",calc(b,d,k)-calc(b,b,k)/2);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注