题解：P1829 [集训队互测 2010] Crash的数字表格 / JZPTAB
shaotianyu
·
·
题解
假定
n\le m
求
P(n,m)=\sum_{i=1}^{n} \sum_{j=1}^m \operatorname{lcm}(i,j)
由
\operatorname{lcm}(i,j)=\frac{ij}{\gcd(i,j)}
改为求
P(n,m)=\sum_{i=1}^{n} \sum_{j=1}^m \frac{ij}{\gcd(i,j)}
枚举 \gcd(i,j) 的取值，改为求
P(n,m)=\sum_{g=1}^n g \sum_{i=1}^{\lfloor \frac{n}{g} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{g} \rfloor } ij[\gcd(i,j)=1]
由
{1(n)*\mu(n)=\varepsilon(n)}
取
n=\gcd(i,j)
则
P(n,m)=\sum_{g=1}^n g \sum_{i=1}^{\lfloor \frac{n}{g} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{g} \rfloor } ij\sum_{d|\gcd(i,j)}\mu(d)
令
S(n,m)=\sum_{i=1}^{\lfloor \frac{n}{g} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{g} \rfloor } ij\sum_{d|\gcd(i,j)}\mu(d)
交换求和次序得
S(n,m)=\sum_{d|\gcd(i,j)}\sum_{i=1}^n \sum_{j=1}^m ij\mu(d)
考虑换为枚举 d，得
S(n,m)=\sum_{d=1}^n\sum_{d|i}^n \sum_{d|j}^m ij\mu(d)
等价于
S(n,m)=\sum_{d=1}^n \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{d} \rfloor} ij\mu(d)d^2
整理得
S(n,m)=\sum_{d=1}^n \mu(d)d^2\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{d} \rfloor} ij
考虑令
T(n,m)=\sum_{i=1}^{n} \sum_{j=1}^{m} ij
求和得
T(n,m)=\frac{n(n+1)m(m+1)}{4}
则
S(n,m)=\sum_{d=1}^n \mu(d)d^2T({\lfloor \frac{n}{d} \rfloor},{\lfloor \frac{m}{d} \rfloor})
代回原目标式
P(n,m)=\sum_{g=1}^n g S({\lfloor \frac{n}{d} \rfloor},{\lfloor \frac{m}{d} \rfloor})
代码：
```cpp
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define int long long
using namespace std;
const int N=1e7+91,mod=20101009;
int not_prime[N],miu[N],pre[N];
vector <int> prime;
void get_miu(int n){
miu[1]=1,not_prime[1]=1;
rep(i,2,n){
if(!not_prime[i]){
miu[i]=-1;
prime.push_back(i);
}
for(auto v:prime){
if(i*v>n) break;
not_prime[i*v]=1;
if(i%v==0){
miu[i*v]=0;
break;
}
miu[i*v]=-miu[i];
}
}
}
int T(int n,int m){
return ((n*(n+1)/2)%mod)*((m*(m+1)/2)%mod)%mod;
}
int S(int n,int m){
int sum=0,l=1,r=1;
while(l<=n){
r=min((n/(n/l)),(m/(m/l)));
sum=(sum+(pre[r]-pre[l-1]+mod)%mod*T(n/l,m/l)%mod)%mod;
l=r+1;
}
return sum;
}
signed main(){
int n,m;
cin>>n>>m;
if(n>m) swap(n,m);
get_miu(1e7);
rep(i,1,n) pre[i]=(pre[i-1]+i*i*miu[i]+mod)%mod;
int sum=0,l=1,r=1;
while(l<=n){
r=min((n/(n/l)),(m/(m/l)));
sum=(sum+(((r-l+1)*(l+r)/2)%mod)*S(n/l,m/l)%mod)%mod;
l=r+1;
}
cout<<sum;
return 0;
}
```