hdu1695 GCD

题目描述

给出 a,b,c,d,e (a=1,c=1)

求
\sum_{i=1}^b\sum_{j=1}^d[\gcd(i,j)=e]
令 n=\lfloor \frac{b}{e}\rfloor ，m=\lfloor \frac{d}{e}\rfloor ，

即求
\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=1]
考虑令 f(d)=\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=d]

那么F(x)=\sum\limits{x|d}f(d)

F(d) 表示有多少 (i,j) ，1\leq i\leq n , 1\leq j \leq m 满足 gcd(i,j)=d 的倍数

显然有 F(d)= \lfloor\frac{n}{d}\rfloor\times \lfloor \frac{m}{d} \rfloor

根据莫比乌斯反演，有
f(n)=\sum_{n|d}\mu(\frac{d}{n})F(d)
求出 f(1) 即可。

因为将 (x,y) 与 (y,x) 看成了同一数对，所以我们不妨设刚才求出的答案为 a(b,d)

题目所求答案为 ：a(b,d)-a(b,b)/2

只求建箭头方向从左指向右的贡献

#include<bits/stdc++.h>
const int maxn = 1e5+10;
bool vis[maxn];
int prime[maxn];
int Mob[maxn];
int g[maxn];
void Mobius_sieve(){
     int cnt = 0;
     vis[1] = 1;
     Mob[1] = 1;
     for(int i = 2; i < maxn; i++){
        if(!vis[i])
            prime[cnt++] = i, Mob[i] = - 1 , g[i] = 1;
        for(int j = 0; j < cnt && 1LL * prime[j] * i < maxn; j++){
            vis[prime[j] * i] = 1;
            g[prime[j]*i] = g[i] + 1;
            Mob[i * prime[j]] = (i % prime[j] ? -Mob[i]: 0);
            if(i % prime[j] == 0)
                break;
        }
    }
}
int main(){
    Mobius_sieve();
    int k=0,t,a,b,c,d,e;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%d%d%d",&a,&b,&c,&d,&e);
        if(e==0){
            printf("Case %d: %lld\n",++k,0ll);
            continue;
        }
        c=b,d=d;
        long long f_1 = 0 ,_f_1 = 0 ;
        if(c>d) std::swap(c,d); 
        for(int i=e;i<=c;i+=e){
            f_1+= Mob[i/e] * (1ll*(c/i)*(d/i));
        }
        for(int i=e;i<=c;i+=e){
            _f_1+= Mob[i/e] * (1ll*(c/i)*(c/i)); 
        }
        printf("Case %d: %lld\n",++k,f_1-_f_1/2);
    }
    return 0;
}