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);
}
}
0 条评论