【题解】BZOJ 2820 YY的GCD

请注意,本文编写于 136 天前,最后修改于 136 天前,其中某些信息可能已经过时。

Probelm

求 $\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j==prime)]$

Thought

莫比乌斯反演练习题

$$ \sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=prime]\\ \sum_{p=1}^{n}[p=prime]\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{p}\rfloor}[gcd(i,j)=1]\\ $$

法1

$f(x)=\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{p}\rfloor}[gcd(i,j)=x]\\$
$g(x)=\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{p}\rfloor}[x|gcd(i,j)]\\$

显然有 $g(x)=\sum_{x|d}^{\lfloor\frac{n}{p}\rfloor}f(d)$
反演可得 $f(x)=\sum_{x|d}^{\lfloor\frac{n}{p}\rfloor}\mu(\frac{d}{x})g(d)$

在函数 $g$ 中,变形可得 $g(t)=\sum_{i=1}^{\lfloor\frac{n}{tp}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{tp}\rfloor}[1|gcd(i,j)]=\lfloor\frac{n}{tp}\rfloor*\lfloor\frac{m}{tp}\rfloor$

那么 $f(t)=\sum_{t|d}^{\lfloor\frac{n}{p}\rfloor}\mu(\frac{d}{t})\lfloor\frac{n}{dp}\rfloor*\lfloor\frac{m}{dp}\rfloor$

原式化为

$$ \sum_{p=1}^{n}[p=prime]\sum_{d=1}^{\lfloor\frac{n}{p}\rfloor}\mu(d)\lfloor\frac{n}{dp}\rfloor\lfloor\frac{m}{dp}\rfloor $$

法2

$$ \sum_{d|n}\mu(d)=\begin{cases} 1 &n=1\\ 0 &otherwise \end{cases} $$

那么 $[gcd(i,j)=1]\Leftrightarrow\sum_{d|gcd(i,j)}\mu(d)$

$$ \sum_{p=1}^{n}[p=prime]\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{p}\rfloor}\sum_{d|gcd(i,j)}\mu(d)\\ $$

枚举 $t$,将 $i,j$ 用 $t$ 的倍数表示

$$ \sum_{p=1}^{n}[p=prime]\sum_{d=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{i=1}^{\lfloor\frac{n}{dp}\rfloor}\sum_{i=1}^{\lfloor\frac{m}{dp}\rfloor}\mu(d)\\ \sum_{p=1}^{n}[p=prime]\sum_{d=1}^{\lfloor\frac{n}{p}\rfloor}\mu(d)\lfloor\frac{n}{dp}\rfloor\lfloor\frac{m}{dp}\rfloor $$

两个式子显然是相同的...

接着,设 $T=tp$,枚举 $T$,$p$ 为 $T$ 的因数

$$ \sum_{T=1}^{n}\sum_{p|T}[p=prime]\mu(\frac{T}{p})\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\\ \sum_{T=1}^{n}\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum_{p|T}[p=prime]\mu(\frac{T}{p}) $$

$\sum_{p|T}[p=prime]\mu(\frac{T}{p})$ 可以用埃氏筛将其筛出,然后做成前缀和的形式就可以数论分块了

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 10000010;

bool np[N];
int pri[N] , tot;
int mu[N] , f[N] , sum[N];
int n , m;
int read() {
    int ans = 0 , flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
void prepare() {
    mu[1] = 1;
    for(int i = 2 ; i < N ; ++ i) {
        if(!np[i]) {
            pri[++ tot] = i;
            mu[i] = - 1;
        }
        for(int j = 1 ; j <= tot && pri[j] * i < N ; ++ j) {
            np[i * pri[j]] = 1;
            if(!(i % pri[j])) break;
            mu[i * pri[j]] = - mu[i];
        }
    }
    for(int i = 1 ; i <= tot ; ++ i)
        for(int j = pri[i] ; j < N ; j += pri[i])
            f[j] += mu[j / pri[i]];
    for(int i = 1 ; i < N ; ++ i)
        f[i] += f[i - 1];
}
int main() {
    prepare();
    int T = read();
    while(T --) {
        n = read(); m = read();
        if(n > m) swap(n , m);
        long long ans = 0;
        int pos = 0;
        for(int i = 1 ; i <= n ; i = pos + 1) {
            pos = min(n / (n / i) , m / (m / i));
            ans += 1ll * (f[pos] - f[i - 1]) * (n / i) * (m / i);
        }
        printf("%lld\n" , ans);
    }
    return 0;
}
Comments

添加新评论