第一道自己认真做的数论

有两种方法，默认\((N<M)\)

方法一：

我们需要求：\[\sum\limits_{i=1}^N \sum\limits_{j=1}^M [gcd(i,j)=prime]\]

我们会想到枚举其中的素数：\[\sum\limits_{p\ \epsilon \ \ prime} \sum\limits_{i=1}^N \sum\limits_{j=1}^M [gcd(i,j)=p]\]

再一步变形：\[\sum\limits_{p\ \epsilon \ \ prime} \sum\limits_{i=1}^N \sum\limits_{j=1}^M [gcd(\frac{i}{p},\frac{j}{p})=1]\]

\[\sum\limits_{p\ \epsilon \ \ prime} \sum\limits_{i=1}^{\left\lfloor \frac{N}{p} \right\rfloor} \sum\limits_{j=1}^{\left\lfloor\frac{M}{p}\right\rfloor} [gcd(i,j)=1]\]

是不是看到中括号里面的东西想到了什么？莫比乌斯函数~~

因为莫比乌斯函数的性质：\[\sum\limits_{d|n} \mu (d)=[n=1]\]

所以原式可化为：\[\sum\limits_{p\ \epsilon \ \ prime} \sum\limits_{i=1}^{\left\lfloor\frac{N}{p}\right\rfloor} \sum\limits_{j=1}^{\left\lfloor\frac{M}{p}\right\rfloor} \sum\limits_{d|gcd(i,j)} \mu (d)\]

我们按照套路把\(d\)提前，其中\(d|gcd(i,j)\)这个条件可以转化成\(d|i,d|j\)，我们就枚举\(d\)：\[\sum\limits_{p\ \epsilon \ \ prime} \sum\limits_{d=1}^{\left\lfloor\frac{N}{p}\right\rfloor} \mu (d) \sum\limits_{i=1}^{\left\lfloor\frac{N}{p}\right\rfloor} [d|i] \sum\limits_{j=1}^{\left\lfloor\frac{M}{p}\right\rfloor} [d|j]\]

根据整出分块，没学过的可以看看我的其他博客，我们就可以把最后两个\(\sum\)消去了：\[\sum\limits_{p\ \epsilon \ \ prime} \sum\limits_{d=1}^{\left\lfloor\frac{N}{p}\right\rfloor} \mu (d) \left\lfloor \frac{N}{d\times p} \right\rfloor \left\lfloor \frac{M}{d\times p} \right\rfloor\]

这里我们再用一个小技巧，我们用\(T\)代替\(d\times p\)：

\[\sum\limits_{p\ \epsilon \ \ prime} \sum\limits_{T=1}^N \mu (\frac{T}{p}) \left\lfloor \frac{N}{T} \right\rfloor \left\lfloor \frac{M}{T} \right\rfloor\]

稍微变一下：\[\sum\limits_{T=1}^N \sum\limits_{p\ \epsilon \ \ prime} \mu (\frac{T}{p}) \left\lfloor \frac{N}{T} \right\rfloor \left\lfloor \frac{M}{T} \right\rfloor\]

这样的话，我们就先线性筛出\(\mu\)函数，然后把\(\sum\limits_{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\n",ans);
    }
    return 0;
}

P2257 YY的GCD

原文：https://www.cnblogs.com/yexinqwq/p/11104889.html