Chlience

【题解】BZOJ 2154 Crash的数字表格
Probelm求 $\sum_{i=1}^{n}\sum_{j=1}^{m}LCM(i,j)$Thought莫比乌...
扫描右侧二维码阅读全文
07
2019/01

【题解】BZOJ 2154 Crash的数字表格

Probelm

求 $\sum_{i=1}^{n}\sum_{j=1}^{m}LCM(i,j)$

Thought

莫比乌斯反演练习题

$$ \sum_{i=1}^{n}\sum_{j=1}^{m}LCM(i,j)\\ \sum_{i=1}^{n}\sum_{j=1}^{m}\frac{i*j}{gcd(i,j)}\\ \sum_{d=1}^{n}\sum_{i=1}^{n}\sum_{j=1}^{m}\frac{ij}{d}[gcd(i,j)=d]\\ \sum_{d=1}^{n}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}dij[gcd(i,j)=1]\\ \sum_{d=1}^{n}d\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}ij[gcd(i,j)=1] $$

法1

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

显然有 $g(x)=\sum_{x|d}^{\lfloor\frac{n}{d}\rfloor}f(t)$

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

在函数 $g$ 中,变形可得 $g(t)=\sum_{i=1}^{\lfloor\frac{n}{dt}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{dt}\rfloor}it*jt=t^2*\sum_{i=1}^{\lfloor\frac{n}{dt}\rfloor}i(\frac{(1+\lfloor\frac{m}{dt}\rfloor)\lfloor\frac{m}{dt}\rfloor}{2})=t^2(\frac{(1+\lfloor\frac{n}{dt}\rfloor)\lfloor\frac{n}{dt}\rfloor}{2})(\frac{(1+\lfloor\frac{m}{dt}\rfloor)\lfloor\frac{m}{dt}\rfloor}{2})$

那么 $f(x)=\sum_{x|t}^{\lfloor\frac{n}{d}\rfloor}\mu(\frac{t}{x})t^2(\frac{(1+\lfloor\frac{n}{dt}\rfloor)\lfloor\frac{n}{dt}\rfloor}{2})(\frac{(1+\lfloor\frac{m}{dt}\rfloor)\lfloor\frac{m}{dt}\rfloor}{2})$

原式化为

$$ \sum_{d=1}^{n}d\sum_{t=1}^{\lfloor\frac{n}{d}\rfloor}\mu(t)t^2(\frac{(1+\lfloor\frac{n}{dt}\rfloor)\lfloor\frac{n}{dt}\rfloor}{2})(\frac{(1+\lfloor\frac{m}{dt}\rfloor)\lfloor\frac{m}{dt}\rfloor}{2}) $$

法2

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

$$ \sum_{d=1}^{n}d\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}ij\sum_{t|gcd(i,j)}\mu(t) $$

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

$$ \sum_{d=1}^{n}d\sum_{t=1}^{\lfloor\frac{n}{d}\rfloor}\mu(t)\sum_{i=1}^{\lfloor\frac{n}{dt}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{dt}\rfloor}it*jt\\ \sum_{d=1}^{n}d\sum_{t=1}^{\lfloor\frac{n}{d}\rfloor}\mu(t)t^2\sum_{i=1}^{\lfloor\frac{n}{dt}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{dt}\rfloor}ij\\ \sum_{d=1}^{n}d\sum_{t=1}^{\lfloor\frac{n}{d}\rfloor}\mu(t)t^2(\frac{(1+\lfloor\frac{n}{dt}\rfloor)\lfloor\frac{n}{dt}\rfloor}{2})(\frac{(1+\lfloor\frac{m}{dt}\rfloor)\lfloor\frac{m}{dt}\rfloor}{2}) $$

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

接着,设 $T=dt$,枚举 $T$,$d$ 为 $T$ 的因数

$$ \sum_{T=1}^{n}d\sum_{d|T}\mu(\frac{T}{d})(\frac{T}{d})^2(\frac{(1+\lfloor\frac{n}{T}\rfloor)\lfloor\frac{n}{T}\rfloor}{2})(\frac{(1+\lfloor\frac{m}{T}\rfloor)\lfloor\frac{m}{T}\rfloor}{2})\\ \sum_{T=1}^{n}(\frac{(1+\lfloor\frac{n}{T}\rfloor)\lfloor\frac{n}{T}\rfloor}{2})(\frac{(1+\lfloor\frac{m}{T}\rfloor)\lfloor\frac{m}{T}\rfloor}{2})\sum_{d|T}\mu(\frac{T}{d})\frac{T^2}{d} $$

$\sum_{d|T}\mu(\frac{T}{d})\frac{T^2}{d}$ 就是 $T\sum_{d|T}d*\mu(d)$

那么设 $F[T]=\sum_{d|T}d*\mu(d)$

发现当 $a,b$ 互质时,有 $F[a]*F[b]=F[ab]$,那么,这是一个积性函数,可以用欧拉筛解决

$$ F[prime]=1-prime\\ F[i*prime]= \begin{cases} F[i]*(1-prime) & i \not\equiv 0\pmod {prime}\\ F[i] & i \equiv 0\pmod {prime}\\ \end{cases} $$

然后将 $T*F[T]$ 做成前缀和的形式就可以数论分块了

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 10000010;
const int mod = 20101009;
bool np[N];
int pri[N] , tot;
int f[N] , s[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;
}
int M(int x) {return (x % mod + mod) % mod;}
void prepare() {
    f[1] = 1;
    for(int i = 2 ; i < N ; ++ i) {
        if(!np[i]) {
            pri[++ tot] = i;
            f[i] = M(1 - i);
        }
        for(int j = 1 ; j <= tot && i * pri[j] < N ; ++ j) {
            np[i * pri[j]] = 1;
            if(i % pri[j])
                f[i * pri[j]] = 1ll * f[i] * f[pri[j]] % mod;
            else {
                f[i * pri[j]] = f[i];
                break;
            }
        }
    }
    for(int i = 1 ; i < N ; ++ i) {
        f[i] = M(1ll * f[i] * i % mod + f[i - 1]);
        s[i] = M(s[i - 1] + i);
    }
}
int main() {
    prepare();
    n = read(); m = read();
    if(n > m) swap(n , m);
    int pos = 0 , ans = 0;
    for(int i = 1 ; i <= n ; i = pos + 1) {
        pos = min(n / (n / i) , m / (m / i));
        ans = M(ans + 1ll * M(f[pos] - f[i - 1]) * s[n / i] % mod * s[m / i] % mod);
    }
    printf("%d\n" , ans);
    return 0;
}
Last modification:January 7th, 2019 at 03:03 pm

Leave a Comment