【题解】Luogu P2257【YY的GCD】

分析

通过$f(n)=\sum_{n|d}\mu(\frac{d}{n})F(d)$,然后设$f(x)$为$gcd(a,b)=x$的对数,$F(x)$为$x|gcd(a,b)$的对数,用莫比乌斯反演第二条可以求出式子:

f(x)=\sum_{x|d}\mu(\frac{d}{x})\frac{n}{d}\times \frac{m}{d}

再令上一个式子中的$x=p,d=pi$可得:

ans=\sum_{isprime(p)}^{n}\sum_{i}^{n}(\frac{n}{ip})(\frac{m}{ip})\mu(i)

意会一下就可以发现,假如设$T=ip$,那么就有:

ans=\sum_{T}^{n}(\frac{n}{T})(\frac{m}{T})\sum_{p|T\ and\ isprime(p)}\mu(Tp)

这样我们预处理一下后面那团东西的前缀和即可,就这样。

代码

#include<cstdio>
#include<algorithm>
using std::fill;using std::swap;
typedef long long int64;

namespace IO{
    inline int read(){
        int ans = 0;char s = getchar();
        while(s < '0' || s > '9'){s = getchar();}
        while(s >= '0' && s <='9'){ans = ans * 10 + s - '0';s = getchar();}
        return ans;
    }
    void print(int64 x){
        if(x > 9){print(x / 10);}
        putchar(x % 10 + '0');
    }
    void println(int64 x){print(x);putchar('\n');}
}
using namespace IO;

const int MAXN = 10000000 + 6;
int primes[MAXN],num,mu[MAXN],sum[MAXN],g[MAXN];
bool isPrime[MAXN];
inline int min(int a,int b){return a < b ? a : b;}
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];
        }
    }
    for(int i = 0;i < num;i++)
        for(int j = 1;primes[i] * j < MAXN;j++)
            sum[primes[i] * j] += mu[j];
    for(int i = 1;i < MAXN;i++) sum[i] = sum[i - 1] + sum[i]; 
}

int64 f(int n,int m){
    if(n > m) swap(n,m);
    int64 ans = 0;
    for(int i = 1,last;i <= n;i = last + 1){
        last = min(n / (n / i),m / (m / i));
        ans += (int64)((sum[last] - sum[i - 1]) * (int64)(n / i) * (int64)(m / i));
    }
    return ans;
}

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out2.txt","w",stdout);
    sieve();
    int T = read(),n,m;
    while(T--){
        n = read(),m = read();int64 ans = f(n,m);
        println(ans);
    }

    return 0;
}

发布者:Cinema

成功的道路并不狭窄,因为大部分人都在颓废。

留下评论

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