洛谷题目链接
第一道自己认真做的数论
有两种方法，默认((N<M))
方法一：
我们需要求：$$sumlimits_{i=1}^N sumlimits_{j=1}^M [gcd(i,j)=prime]$$
我们会想到枚举其中的素数：$$sumlimits_{p epsilon prime} sumlimits_{i=1}^N sumlimits_{j=1}^M [gcd(i,j)=p]$$
再一步变形：$$sumlimits_{p epsilon prime} sumlimits_{i=1}^N sumlimits_{j=1}^M [gcd(frac{i}{p},frac{j}{p})=1]$$
是不是看到中括号里面的东西想到了什么？莫比乌斯函数~~
因为莫比乌斯函数的性质：$$sumlimits_{d|n} mu (d)=[n=1]$$
所以原式可化为：$$sumlimits_{p epsilon prime} sumlimits_{i=1}^{leftlfloorfrac{N}{p} ight floor} sumlimits_{j=1}^{leftlfloorfrac{M}{p} ight floor} sumlimits_{d|gcd(i,j)} mu (d)$$
我们按照套路把(d)提前，其中(d|gcd(i,j))这个条件可以转化成(d|i,d|j)，我们就枚举(d)：$$sumlimits_{p epsilon prime} sumlimits_{d=1}^{leftlfloorfrac{N}{p} ight floor} mu (d) sumlimits_{i=1}^{leftlfloorfrac{N}{p} ight floor} [d|i] sumlimits_{j=1}^{leftlfloorfrac{M}{p} ight floor} [d|j]$$
根据整出分块，没学过的可以看看我的其他博客，我们就可以把最后两个(sum)消去了：$$sumlimits_{p epsilon prime} sumlimits_{d=1}^{leftlfloorfrac{N}{p} ight floor} mu (d) leftlfloor frac{N}{d imes p} ight floor leftlfloor frac{M}{d imes p} ight floor$$
这里我们再用一个小技巧，我们用(T)代替(d imes p)：
稍微变一下：$$sumlimits_{T=1}^N sumlimits_{p epsilon prime} mu (frac{T}{p}) leftlfloor frac{N}{T} ight floor leftlfloor frac{M}{T} ight floor$$
这样的话，我们就先线性筛出(mu)函数，然后把(sumlimits_{p epsilon prime} mu (frac{T}{p}))处理出来，做一下前缀和，就可以用整除分块来(O(sqrt n))回答每个询问了
接下来是美滋滋的代码时间~~~
#include<iostream>
#include<cstdio>
#define N 10000007
#define int long long
using namespace std;
int T,n,m,ans,cnt;
int mu[N],prime[N>>2],num[N];
bool isp[N];
void Get_mu()
{
mu[1]=1;
for(int i=2;i<=N-7;++i)
{
if(!isp[i])
{
prime[++cnt]=i;
mu[i]=-1;
}
for(int j=1;j<=cnt&&(prime[j]*i)<=N-7;++j)
{
isp[i*prime[j]]=1;
if(i%prime[j]==0)
break;
else
mu[i*prime[j]]=-mu[i];
}
}
for(int i=1;i<=cnt;++i)
{
int res=1;
for(int j=prime[i];j<=N-7;j+=prime[i],++res)
num[j]+=mu[res];
}
for(int i=2;i<=N-7;++i)
num[i]+=num[i-1];
}
signed main()
{
Get_mu();
scanf("%lld",&T);
while(T--)
{
scanf("%lld%lld",&n,&m);
if(n>m)
swap(n,m);
ans=0;
for(int l=1,r;l<=n;l=r+1)
{
r=min(n/(n/l),m/(m/l));
ans+=(num[r]-num[l-1])*(n/l)*(m/l);
}
printf("%lld
",ans);
}
return 0;
}
方法二：
我们要求：$$sumlimits_{i=1}^N sumlimits_{j=1}^M [gcd(i,j)=prime]$$
我们设(F(d))表示(d|gcd(i,j))且(1<=i<=N,1<=j<=M)的((i,j))对数
很明显：$$F(d)=sumlimits_{i=1}^N sumlimits_{j=1}^M [d|gcd(i,j)]$$
(d|gcd(i,j))可以化为(d|i,d|j)：$$F(d)=sumlimits_{i=1}^N [d|i] sumlimits_{j=1}^M [d|j]$$
我们再设(f(d))表示(gcd(i,j)=d)且(1<=i<=N,1<=j<=M)的((i,j))对数
可得$$F(d)=sumlimits_{d|n}^N f(n)$$
莫比乌斯反演得：$$f(d)=sumlimits_{d|n}^N mu (frac{n}{d}) F(n)$$
而我们题目中就是要求：$$Ans=sumlimits_{p epsilon prime} f(p)$$
把(f(p))带入：$$Ans=sumlimits_{p epsilon prime} sumlimits_{p|d} mu (frac{d}{p}) leftlfloor frac{N}{d} ight floor leftlfloor frac{M}{d} ight floor$$
我们改为枚举(frac{d}{p})：$$Ans=sumlimits_{p epsilon prime} sumlimits_{d=1}^{leftlfloor frac{N}{p} ight floor} mu (d) leftlfloor frac{N}{d imes p} ight floor leftlfloor frac{M}{d imes p} ight floor$$
那么再像上面那个方法一样用(T)代替(d imes p)即可
代码也是一样的~~~