Luogu2568 GCD

题目链接：Link

### 题意

给定整数N，求 $1<=x,y<=N$ 且 $Gcd(x,y)$ 为素数的数对 $(x,y)$ 有多少对. (这个就是题面233333)

### 题解

~~很水的一道数论题~~

因为一个有序数对 $(x,y)$ 的 $GCD$ 若要是一个质数，那么必然的，$x, y$ 中必有一个是质数，否则不存在 $GCD$ 是质数的可能（自行思考，很简单）。

那么对于每一个质数 $p$ ，它的答案贡献就是 $(1$ ~ $frac{n}{p}) $

对 $y$ 的取值范围进行讨论，当 $y = x $ 时， 有且仅有 $ y = x = 1$ 时 $x | y$

​ 当 $y > x$ 时， 答案显然为$varphi (y)$

最后的答案为所以有序互质对的个数为 $(1$ ~ $frac{n}{p}) $ 的欧拉函数之和乘2减1（要求的是有序互质对，因为有正反所以乘2以后减去（1， 1）多算的一次）

### Code

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int SIZE = 1e7 + 5;

int n, p, tot;
int phi[SIZE], prime[SIZE], vis[SIZE];
LL ans, sum[SIZE];

inline void Euler()
{
    phi[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (!vis[i]) { phi[i] = i - 1; prime[++tot] = i; }
        for (int j = 1; j <= tot; j++)
        {
            int x = prime[j];
            if (i * x > n) break;
            vis[i * x] = 1;
            if (i % x == 0) { phi[i * x] = phi[i] * x; break; }
            else phi[i * x] = phi[i] * phi[x];
        }
    }
}

int main()
{
    scanf("%d", &n);
    Euler();
    for (int i = 1; i <= n; i++)
        sum[i] = sum[i - 1] + phi[i];
    for (int i = 1; i <= tot; i++)
        ans += sum[n / prime[i]] * 2 - 1;
    printf("%lld", ans);
    return 0;
}