洛谷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;
}