【题解】HDOJ P1695【GCD】

背景

Cinema又重拾莫比乌斯反演了

分析

这差不多就是个板题,不过要减去重复的,还要处理$k==0$的情况

代码

#include<cstdio>
#include<algorithm>
using std::fill;using std::swap;
typedef long long int64;
const int MAXN = 1000000 + 6;
int primes[MAXN],mu[MAXN],num;
bool isPrime[MAXN];

void sieve(){
    fill(isPrime,isPrime + MAXN,true);
    num = 0;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];
        }
    }
}

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out2.txt","w",stdout);
    sieve();
    int T,a,b,c,d,k,id = 1;scanf("%d",&T);
    while(T--){
        scanf("%d %d %d %d %d",&a,&b,&c,&d,&k);
        if(k == 0){printf("Case %d: 0\n",id++);continue;}
        int ans = 0,ans2 = 0;
        if(b > d) swap(b,d);
        b /= k,d /= k;
        for(int i = 1;i <= b;i++) ans += (int64)mu[i] * (b / i) * (d / i),ans2 += (int64)mu[i] * (b / i) * (b / i);;
        printf("Case %d: %d\n",id++,ans - ans2 / 2);
    }

    return 0;
}