前置知识
解法
令 \(n \le m\)。
考虑莫比乌斯反演,推式子,有 \(\begin{aligned} &\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\operatorname{lcm}(i,j) \\ &=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\frac{ij}{\gcd(i,j)} \\ &=\sum\limits_{k=1}^{n}\frac{1}{k}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}ij[\gcd(i,j)=k] \\ &=\sum\limits_{k=1}^{n}\frac{1}{k}\sum\limits_{i=1}^{\left\lfloor \frac{n}{k} \right\rfloor}\sum\limits_{j=1}^{\left\lfloor \frac{m}{k} \right\rfloor}ijk^{2}[\gcd(i,j)=1] \\ &=\sum\limits_{k=1}^{n}k\sum\limits_{i=1}^{\left\lfloor \frac{n}{k} \right\rfloor}\sum\limits_{j=1}^{\left\lfloor \frac{m}{k} \right\rfloor}ij\sum\limits_{d|\gcd(i,j)}\mu(d) \\ &=\sum\limits_{k=1}^{n}k\sum\limits_{d=1}^{n}\mu(d)\sum\limits_{i=1}^{\left\lfloor \frac{n}{k} \right\rfloor}\sum\limits_{j=1}^{\left\lfloor \frac{m}{k} \right\rfloor}ij[d|\gcd(i,j)] \\ &=\sum\limits_{k=1}^{n}k\sum\limits_{d=1}^{n}\mu(d)d^{2}\sum\limits_{i=1}^{\left\lfloor \frac{n}{kd} \right\rfloor}\sum\limits_{j=1}^{\left\lfloor \frac{m}{kd} \right\rfloor}ij \\ &=\sum\limits_{k=1}^{n}k\sum\limits_{d=1}^{n}\mu(d)d^{2}\sum\limits_{i=1}^{\left\lfloor \frac{n}{kd} \right\rfloor}i\sum\limits_{j=1}^{\left\lfloor \frac{m}{kd} \right\rfloor}j \\ &=\sum\limits_{T=1}^{n}T\sum\limits_{d|T}\mu(d)d\sum\limits_{i=1}^{\left\lfloor \frac{n}{T} \right\rfloor}i\sum\limits_{j=1}^{\left\lfloor \frac{m}{T} \right\rfloor}j \end{aligned}\)。
\(f(n)=\sum\limits_{d|n}\mu(d)d\) 显然是积性函数,线筛筛一下即可。
接着维护前缀和后整除分块。
需要注意的是本题仅限 C++98 提交。
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define sort stable_sort
#define endl '\n'
const ll p=20101009;
ll prime[10000010],vis[10000010],miu[10000010],f[10000010],sum[10000010],s[10000010],len=0;
void isprime(ll n)
{
memset(vis,0,sizeof(vis));
miu[1]=1;
f[1]=1;
for(ll i=2;i<=n;i++)
{
if(vis[i]==0)
{
len++;
prime[len]=i;
miu[i]=-1;
f[i]=1-i;
}
for(ll j=1;j<=len&&i*prime[j]<=n;j++)
{
vis[i*prime[j]]=1;
if(i%prime[j]==0)
{
miu[i*prime[j]]=0;
f[i*prime[j]]=f[i];
break;
}
else
{
miu[i*prime[j]]=-miu[i];
f[i*prime[j]]=f[i]*f[prime[j]];
}
}
}
for(ll i=1;i<=n;i++)
{
s[i]=(s[i-1]+i)%p;
sum[i]=(sum[i-1]+f[i]*i%p+p)%p;
}
}
ll ask(ll n,ll m)
{
ll ans=0,l,r;
for(l=1,r;l<=n;l=r+1)
{
r=min(n/(n/l),m/(m/l));
ans=(ans+(s[n/l]*s[m/l]%p)*(sum[r]-sum[l-1]+p)%p)%p;
}
return ans;
}
int main()
{
ll n,m;
cin>>n>>m;
isprime(max(n,m));
if(n>m)
{
swap(n,m);
}
cout<<ask(n,m)<<endl;
return 0;
}
后记
多倍经验:luogu P1829 [国家集训队] Crash的数字表格 / JZPTAB
标签:lfloor,right,frac,limits,题解,sum,rfloor,SP8099,Crash From: https://www.cnblogs.com/The-Shadow-Dragon/p/18333249