洛谷P2568 GCD 题解

题目链接：P2568 GCD

题意：

给定正整数 \(n\)，求 \(1\le x,y\le n\) 且 \(\gcd(x,y)\)为素数的数对 \((x,y)\) 有多少对。

\(1 \le n\le 10^7\)

正着去想不太好搞，那就反过来

考虑一个素数对答案的贡献

显然所有满足条件的 \((x,y)\) 都可以写作 \((ap_i,bp_i)\) 的形式，其中 \(\gcd(x,y)=p_i\)

注意到 \(\gcd(a,b)=1\)

则对于每个素数 \(p\ (p\le n)\) ，它对答案的贡献就是 \[ 2\sum\limits_{i=1}^{k}\varphi(i)-1 \] 其中，\(k=\left\lfloor\dfrac{n}{p}\right\rfloor\)， \(\varphi(n)\) 为欧拉函数

\(\times 2\) 是因为 \((x,y)\) 为有序点对，\(-1\) 是因为 \((1,1)\) 会被多算一次

直接线性筛 \(\varphi(n)\) 然后前缀和一下就好了

时间复杂度 \(O(n)\) ，记得开 \(\text{long long}\) 哦

代码如下

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e7+15)
int prime[N],pcnt,phi[N],sum[N];
bool ck[N];
void Euler(int n)
{
    phi[1]=1;ck[1]=1;
    for(int i=2; i<=n; i++)
    {
        if(!ck[i])
        {
            prime[++pcnt]=i;
            phi[i]=i-1;
        }
        for(int j=1; j<=pcnt&&i*prime[j]<=n; j++)
        {
            int pos=i*prime[j];
            ck[pos]=1;
            if(i%prime[j])
            {
                phi[pos]=phi[i]*phi[prime[j]];
            }else 
            {
                phi[pos]=phi[i]*prime[j];
                break;
            }
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n,res=0;
    cin >> n;
    Euler(n);
    for(int i=1; i<=n; i++)
        sum[i]+=sum[i-1]+phi[i];
    for(int i=1; i<=pcnt&&prime[i]<=n; i++)
        res+=sum[n/prime[i]]*2-1;
    cout << res << endl;
    return 0;
}