BZOJ_2820_YY的GCD_莫比乌斯反演
题意&分析：
$\sum\limits_pis[p]\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[gcd(i,j)=p]$
$=\sum\limits_pis[p]\sum\limits_{i=1}^{\lfloor \frac{n}{p}\rfloor}\sum\limits_{j=1}^{\lfloor \frac{m}{p}\rfloor}[gcd(i,j)=1]$
$=\sum\limits_pis[p]\sum\limits_{i=1}^{\lfloor \frac{n}{p}\rfloor}\sum\limits_{j=1}^{\lfloor \frac{m}{p}\rfloor}[gcd(i,j)=1]$
$=\sum\limits_pis[p]\sum\limits_{i=1}^{\lfloor \frac{n}{p}\rfloor}\sum\limits_{j=1}^{\lfloor \frac{m}{p}\rfloor}\sum\limits_{d|gcd(i,j)}\mu(d)$
$=\sum\limits_pis[p]\sum\limits_{d=1}^{\lfloor \frac{n}{p}\rfloor}\mu(d)\sum\limits_{i=1}^{\lfloor \frac{n}{dp}\rfloor}\sum\limits_{j=1}^{\lfloor \frac{m}{dp}\rfloor}$
$=\sum\limits_{Q=1}^{n}\lfloor \frac{n}{Q}\rfloor\lfloor\frac{m}{Q}\rfloor\sum\limits_{p|Q}is[p]\mu(\lfloor\frac{Q}{p}\rfloor)$
$f(n)=\sum\limits_{p|n}is[p]\mu(\lfloor\frac{n}{p}\rfloor)$
首先$f[i]$非积性，但可以通过μ处理，所以我们考虑线筛
1.当$i$为质数时$f[i]=1$;
2.当$i$%$p==0$时
$f(i*p)=\sum\limits_{d|i}is[d]\mu(i*p/d)$
当$d!=p$时$i*p/d$有两个以上的$p$，贡献为$0$，因此此时$f(i*p)=\mu(i)$
3.当$i$%$p!=0$时$i$与$p$互质
$f(i*p)=\sum\limits_{d|i}is[d]\mu(i*p/d)+\sum\limits_{d|p}is[d]\mu(i*p/d)$
$=f(i)*\mu(p)+f(p)*\mu(i)$
$=\mu(i)-f(i)$
再记录下f[i]的前缀和，分块计算
代码：
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long
int prime[4000010],vis[10000100],miu[10000100],f[10000100],sum[10000100],cnt;
int T,n,m;
inline void init()
{
miu[1]=1;
for(int i=2;i<=10000000;i++)
{
if(!vis[i])
{
miu[i]=-1;
f[i]=1;
prime[++cnt]=i;
}
for(int j=1;j<=cnt&&i*prime[j]<=10000000;j++)
{
vis[i*prime[j]]=1;
if(i%prime[j]==0)
{
miu[i*prime[j]]=0;
f[i*prime[j]]=miu[i];
break;
}
miu[i*prime[j]]=-miu[i];
f[i*prime[j]]=miu[i]-f[i];
}
sum[i]=sum[i-1]+f[i];
}
}
int main()
{
init();
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
if(n>m)swap(n,m);
int lst;
LL ans=0;
for(int i=1;i<=n;i=lst+1)
{
lst=min(n/(n/i),m/(m/i));
ans+=1ll*(sum[lst]-sum[i-1])*(n/i)*(m/i);
}
printf("%lld\n",ans);
}
}
