LouguP1829
#include <bits/stdc++.h>
#define sc(p) scanf("%lld",&p)
#define pr(p) printf("%lld\n",p)
const int N=10100000;
const int mod=20101009;
using namespace std;
long long miu[N],prime[N]={0}; bool vis[N]={0};
long long sum[N]={0};
void mobius (int gd)
{
miu[1]=1; for (int i=2; i<=gd; i++) miu[i]=-1;
for (int i=2; i<=gd; i++)
{
if (!vis[i]) prime[++prime[0]]=i,miu[i]=-1;
for (int j=1; j<=prime[0]; j++)
{
int k=i*prime[j]; if (k>gd) break;
vis[k]=1;
if (i%prime[j]==0) { miu[k]=0; break; }
else miu[k]=miu[i]*(-1);
}
}
for (long long i=1; i<=gd; i++) sum[i]=(sum[i-1]+miu[i]%mod*i%mod*i%mod)%mod;
}
long long getf (long long n,long long m)
{
return (n*(n+1)/2ll%mod)*(m*(m+1)/2ll%mod)%mod;
}
long long getg (long long n,long long m)
{
long long ans=0;
for (long long i=1; i<=min (n,m);)
{
long long w=min (n/(n/i),m/(m/i));
long long k=(sum[w]-sum[i-1]+mod)%mod;
ans=(ans+k*getf (n/i,m/i)%mod)%mod;
i=w+1;
}
return ans%mod;
}
int main()
{
long long n,m; sc(n),sc(m);
mobius (max (n,m));
long long ans=0;
for (long long d=1; d<=min (n,m);)
{
long long w=min (n/(n/d),m/(m/d));
long long k=(d+w)*(w-d+1)/2%mod;
ans=(ans+k*getg (n/d,m/d)%mod)%mod;
d=w+1;
}
pr(ans);
return 0;
}
莫比乌斯反演
公式
$F(n)=\sum_{d|n}G(d)\Leftrightarrow G(n)=\sum_{d|n}\mu(d)F(\frac{n}{d})$
莫比乌斯函数
定义
$n$=1时,$\mu(n)=1$
$n$为Square-Free数,$k$为质因数个数,$\mu(n)=(-1)^{k}$
$n$不为Square-Free数,$\mu(n)=0$
求法
线性筛，见上。
性质
1.$\sum_{d|n}\mu(d)=\left[n=1\right]$
$\left[…\right]$为布尔表达式
2.待补充……
应用
方法一：利用莫比乌斯函数的性质（以下均采用该方法）。
方法二：构造出像莫比乌斯函数形式的式子。
栗1
求$\sum_{i=1}^n\sum_{j=1}^m gcd(i,j)$
法1
默认$(n<m)$
设$gcd(i,j)=d$
则$i=dx,j=dy$
易得
回顾函数性质：$\sum_{d|n}\mu(d)=\left[n=1\right]$
用$gcd(x,y)$代入$n$，则$\sum_{d|gcd(x,y)}\mu(d)=\left[ gcd(x,y)=1\right]$
再代入开头式子，得
设$x=xx’,y=xy’$,则：
\[\sum_{d=1}^n d\sum_{x=1}^{\frac{n}{d}}\mu(x)\sum_{x=1}^{\frac{n}{dx}}\sum_{y=1}^{\frac{m}{dx}}1=\sum_{d=1}^n d\sum_{x=1}^{\frac{n}{d}}\mu(x)\lfloor\frac{n}{dx}\rfloor\lfloor\frac{m}{dx}\rfloor\]设内层循环为$f(n)=\sum_{i=1}^n \mu(i)\lfloor\frac{n}{i}\rfloor^{2}$
$\lfloor\frac{n}{i}\rfloor$最多只有$2*\sqrt{n}$个取值，可分块。
外层循环同理。总时间$O(n)$。
法2
当题目两个$\sum$都是到$n$时，可以使用$\varphi$，$O(\sqrt{n})$。
法3
LuoguP4449
使用$O(n\ln{n})$（或$O(n)$）预处理，对于每个询问，$O(\sqrt{n})$。
接着上面的
设$T=dk$，则
\[\sum_{T=1}^n\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor \sum_{d|T}d^{k}\mu(\frac{T}{d})\]设内层循环$f(n)=\sum_{d|n}d^{k}\mu(\frac{n}{d})$
由于$f(n)$为积性函数，可以$O(n)$预处理。（正解$<1.3s$）
但本人太菜，暴力求。（$>28s$）
外层分块。
反正过了不是嘛。。
栗2
求$\sum_{i=1}^n\sum_{j=1}^m lcm(i,j)$
%%%梁好强
CC 原创文章采用CC BY-NC-SA 4.0协议进行许可，转载请注明：“转载自：莫比乌斯反演”