P1829 [国家集训队]Crash的数字表格 / JZPTAB

题目描述

求
\sum_{i=1}^n\sum_{j=1}^mlcm(i,j)

Solution

令 n\leq m
\sum_{i=1}^n\sum_{j=1}^mlcm(i,j)=\sum_{i=1}^n\sum_{j=1}^m\frac{i\times j}{(i,j)}

ans=\sum_{p=1}^n\frac{1}{p}\times\sum_{i=1}^{n}\sum_{j=1}^{m}[(i,j)=p]\times (i\times j)

令
f(p)= \sum_{i=1}^n\sum_{j=1}^m[(i,j)=p] \times (i\times j)
不好算，引入莫比乌斯反演
F(d)=\sum_{d|n}f(n)= \sum_{i=1}^n\sum_{j=1}^m[d|(i,j)] \times (i\times j)

F(d)=d^2\sum_{i=1}^{\frac{n}{d}}i\sum_{j=1}^{\frac{m}{d}}j
有
f(d)=\sum_{d|n}\mu(\frac{n}{d})F(x)
所以
ans=\sum_{p=1}^n\frac{1}{p}\times\sum_{p|x}\mu(\frac{x}{p})x^2\sum_{i=1}^{\frac{n}{x}}i\sum_{j=1}^{\frac{m}{x}}j

ans=\sum_{p=1}^n\sum_{p|x}\mu(\frac{x}{p})\frac{x}{p}x\sum_{i=1}^{\frac{n}{x}}i\sum_{j=1}^{\frac{m}{x}}j

更换枚举顺序，枚举 x
ans=\sum_{x=1}^nx\times\sum_{p|x}\mu(\frac{x}{p})\frac{x}{p}\times\sum_{i=1}^{\frac{n}{x}}i\sum_{j=1}^{\frac{m}{x}}j
因为 p 是 x 所有因数，\frac{x}{p} 亦然，所以
\sum_{p|x}\mu(\frac{x}{p})\frac{x}{p}=\sum_{p|x}\mu(p)p
这个函数是积性函数，可以用线性筛预处理

然后加个整除分块，就可以做到 O(n) 预处理，O(\sqrt n) 单词询问了

#include<bits/stdc++.h>
#define ll long long
const ll mod = 20101009;
const int N = 1e7+10;
bool vis[N];
int prime[N];
ll pre[N],ud[N];
void Mobius_sieve(int N){
    int cnt = 0;vis[1] = 1;ud[1] = 1;
    for(int i = 2; i < N; i++){
        if(!vis[i])
            prime[cnt++] = i, ud[i] = 1-i;
        for(int j = 0; j < cnt && 1LL * prime[j] * i < N; j++){
            vis[prime[j] * i] = 1;   
            ud[i*prime[j]] = (i % prime[j]? ud[i]*ud[prime[j]]%mod:ud[i]);
            if(i % prime[j] == 0)
                break;
        }
    }
    for(int i=1;i<N;++i)
        pre[i] = (pre[i-1]+ud[i]*i)%mod;
}
int main(){

    int t = 0 ;
    t=1;
//  scanf("%d",&t);
    while(t--){
        ll ans =0  ;
        int n,m;
        scanf("%d%d",&n,&m);
        if(n>m) std::swap(n,m);
        Mobius_sieve(n+1);
        for(int l=1,r=0;l<=n;l=r+1){
            r = std::min(n,std::min(n/(n/l),m/(m/l)));
            ll x = n/l, y = m/l;
            x = ((x+1)*x>>1)%mod , y = ((y+1)*y>>1)%mod;
            ans = (ans+x*y%mod*(pre[r]-pre[l-1])%mod)%mod;
        }
        ans %= mod;
        ans = (ans+mod)%mod;
        printf("%lld\n",ans);
    }
}