洛谷P2257 YY的GCD 题解

题意：

多组询问。

给定 \(N, M\)，求 \(1 \leq x \leq N\)，\(1 \leq y \leq M\) 且 \(\gcd(x,y)\) 为质数的 \((x,y)\) 有多少对。

一句话题意

令 \(\mathcal{P}\) 为所有素数组成的集合，求 \[ \sum_{i=1}^{n}\sum_{j=1}^{m}\left[\gcd(i,j)\in\mathcal{P}\right] \] 不妨假设 \(n\le m\)

然后么推推柿子

友情提醒，这道题涉及经典操作：转化枚举量、构造莫比乌斯反演

不知道的可以先去看看别的题，比如这个题 link \[ \begin{aligned} &\sum_{i=1}^{n}\sum_{j=1}^{m}\left[\gcd(i,j)\in\mathcal{P}\right] \\= &\sum_{k=1}^{n}\sum_{i=1}^{n}\sum_{j=1}^m\left[\gcd(i,j)=k\right][k \in \mathcal{P}] \\= &\sum_{k=1}^{n}\sum_{i=1}^{\left\lfloor{\frac{n}{k}}\right\rfloor}\sum_{j=1}^{\left\lfloor{\frac{m}{k}}\right\rfloor}[\gcd(i,j)=1][k \in \mathcal{P}] \\=&\sum_{k=1}^{n}\sum_{i=1}^{\left\lfloor{\frac{n}{k}}\right\rfloor}\sum_{j=1}^{\left\lfloor{\frac{m}{k}}\right\rfloor}\sum_{d\mid \gcd(i,j)}\mu(d)[k \in \mathcal{P}] \\=&\sum_{k=1}^{n}\sum_{d=1}^{\left\lfloor{\frac{n}{k}}\right\rfloor}\mu(d)\left\lfloor{\dfrac{n}{kd}}\right\rfloor\left\lfloor{\dfrac{m}{kd}}\right\rfloor[k \in \mathcal{P}] \\=&\sum_{l=1}^{n}\left\lfloor{\dfrac{n}{l}}\right\rfloor\left\lfloor{\dfrac{m}{l}}\right\rfloor\sum_{k \mid l\land k \in \mathcal{P}}\mu\left(\dfrac{l}{k}\right) \end{aligned} \] 注：\(\land\) 表示逻辑与，可认为其等价于 “且”

令 \(f(x) = \sum\limits_{k \mid x\land k \in \mathcal{P}}\mu\left(\dfrac{x}{k}\right)\)

然后这个题其实到这里就差不多了

前面的用数论分块

后面那个 \(\mu\) 可以在筛法里面求

时间复杂度 \(O(n\log \log n + Q\sqrt{n})\)

#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N (int)(1e7+15)
int Q,x,y;
int prime[6000005],mu[N],pcnt,sum[N];
bool ck[N];
void Mobius()
{
    mu[1]=1;
    for(int i=2; i<=N-5; i++)
    {
        if(!ck[i])
        {
            prime[++pcnt]=i;
            mu[i]=-1;
        }
        for(int j=1; j<=pcnt&&i*prime[j]<=N-5; j++)
        {
            int pos=i*prime[j];
            ck[pos]=1;

            if(i%prime[j])
            {
                mu[pos]=-mu[i];
            }else
            {
                mu[pos]=0;
                break;
            }
        }
    }
    for(int i=1; i<=pcnt; i++)
        for(int j=1; prime[i]*j<=N-5; j++)
            sum[j*prime[i]]+=mu[j];
            
    for(int i=1; i<=N-5; i++)
        sum[i]+=sum[i-1];
}
long long solve(int n,int m)
{
    long long res=0;
    for(int l=1,r; l<=min(n,m); l=r+1)
    {
        r=min(n/(n/l),m/(m/l));
        res+=(long long)(sum[r]-sum[l-1])*(n/l)*(m/l);
    }
    return res;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    read(Q);
    Mobius();
    while(Q--)
    {
        read(x);read(y);
        write(solve(x,y));pc('\n');
    }
    return 0;
}

这份代码很慢，跑了7.74s，目前最优解就跑了 5.69s (截止20220511)

其实这个 \(O(n \log\log n)\) 的枚举并没有必要

考虑在线性筛的过程中更新答案 \[ f(x) = \sum\limits_{k \mid x\land k \in \mathcal{P}}\mu\left(\dfrac{x}{k}\right) \] 设 \(x=ab\) ，其中 \(a\) 为 \(x\) 的最小质因数

称 \(p\) 为当前线性筛枚举的一个用于标记的素数（prime[j]）

若 \(x \in \mathcal{P}\) ，则显然 \(f(x) = \mu(1) = 1\)
若 \(x\notin \mathcal P \land b \bmod a = 0\)

则有 \(x = a^p b^{\prime},b=a^{p-1}b^{\prime},p\) 为大于 \(1\) 的正整数（即 \(x\) 有多个最小质因数）
- 若 \(b\) 没有多个最小质因数，则当且仅当 \(p=a\) 时 \(\mu\left(\dfrac{x}{p}\right) = \mu(b) \ne 0\)
  
  因此有 \(f(x) = \mu(b)\)
- 若 \(b\) 含有多个最小质因数，则 \(\forall p \in \mathcal{P}^{\prime},\mu\left(\dfrac{x}{p}\right)=0,\mathcal{P}^{\prime}\) 为当前筛出的素数集
  
  不过我们无须单独考虑这种情况，因为此时仍然有 \(\mu\left(\dfrac{x}{p}\right) = \mu(b)\)
若 \(x\notin \mathcal{P} \land b \bmod a \ne 0\)

则此时 \(x\) 有唯一且最小的质因数 \(a\)

显然有 \(\mu(x) = -\mu(b)\) ，因为它仅仅多了一个本质不同的质因子

则对于 \(\mu\left(\dfrac{x}{p}\right) = -\mu\left(\dfrac{b}{p}\right)\) 也是成立的

因此 \(f(b)\) 中的每一项在 \(f(x)\) 中都能找到对应的

注意到 \[ f(x) = f(ab) =\sum\limits_{k \mid ab\land k \in \mathcal{P}}\mu\left(\dfrac{ab}{k}\right) \] 由于 \(\gcd(a,b)=1\) （显然），则 \(f(x)\) 仅仅比 \(f(b)\) 多了一项 \(\mu\left(\dfrac{ab}{a}\right) = \mu(b)\)

则有 \(f(x) = -f(b)+\mu(b)\)

综上，有 \[ f(x) = \begin{cases} \mu(1),&x \in \mathcal{P}, \\\\\mu(b),&x \notin \mathcal{P} \land b \bmod a=0, \\\\-f(b)+\mu(b),&x\notin \mathcal{P} \land b\bmod a \ne 0. \end{cases} \] 于是我们就可以在 \(O(n + Q\sqrt{n})\) 的时间复杂度内解决这个问题了

~~然后稍微卡一卡常，就跑的飞快~~

~~对了，目前最优解其实是我的代码哦（虽然没啥用~~

代码如下

#include <bits/stdc++.h>
using namespace std;
// #define int long long
typedef long long ll;
#define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N (int)(1e7+15)
int Q,mx,x[10005],y[10005];;
int prime[1000005],mu[N],pcnt,f[N];
bool ck[N];
void Mobius()
{
    mu[1]=1;
    for(int i=2; i<=mx+5; i++)
    {
        if(!ck[i])
        {
            prime[++pcnt]=i;
            mu[i]=-1;
            f[i]=1;
        }
        for(int j=1; j<=pcnt&&i*prime[j]<=mx+5; j++)
        {
            int pos=i*prime[j];
            ck[pos]=1;
            if(i%prime[j])
            {
                f[pos]=-f[i]+mu[i];
                mu[pos]=-mu[i];
            }else
            {
                f[pos]=mu[i];
                mu[pos]=0;
                break;
            }
        }
        f[i]+=f[i-1];
    }
}
ll solve(int n,int m)
{
    ll res=0;
    for(int l=1,r; l<=min(n,m); l=r+1)
    {
        r=min(n/(n/l),m/(m/l));
        res+=(ll)(f[r]-f[l-1])*(n/l)*(m/l);
    }
    return res;
}

signed main()
{
    read(Q);
    for(int i=1; i<=Q; i++)
        read(x[i]),read(y[i]);
    mx=max(*max_element(x+1,x+1+Q),*max_element(y+1,y+1+Q));
    Mobius();
    for(int i=1; i<=Q; i++)
        write(solve(x[i],y[i])),pc('\n');
    return 0;
}