最大公约数

给定整数N，求1<=x,y<=N且GCD(x,y)为素数的数对(x,y)有多少对。

GCD(x,y)即求x，y的最大公约数。

输入格式

输入一个整数N

输出格式

输出一个整数，表示满足条件的数对数量。

数据范围

$1≤N≤10^7$
输入样例：

4

输出样例：

4

思路

对于gcd(a,b) = d，可以得出gcd(a/d,b/d) = 1,也就是两个数除以最大公约数之后必定互质。因为这题的最大公约数只的是质数，所以我们可以枚举质数。现在m枚举到的质数是p，假如x<y，那么y最大就是N/p，那么可以算出与y属于[1,y]互质的个数和(可用前缀和预先算出).
最后x与y交换需要乘以2，然后还要减去x == y的情况(多算了一次)。因为每一次算前缀和都把E[1] = 1 算进去了。
当前也可以把E[1] = 0, 最后再加上x == y 的情况

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e7+10;
typedef long long ll;

int P[maxn],tail;
bool vis[maxn];
int E[maxn];
ll sum[maxn];
int N;
void initEP(int n)
{
    E[1] = 1;
    for (int i = 2; i <n; i ++ ){
        if (!vis[i]){
            P[tail ++ ] = i;
            E[i] = i-1;
        }
        for (int j = 0; P[j] * i <= n; j ++ ){
            vis[P[j] * i] = true;
            if (i % P[j] == 0){
                E[i * P[j]] = E[i] * P[j];
                break;
            }
            E[i * P[j]] = E[i] * (P[j] - 1);
        }
    }

    for (int i = 1; i <= n; i ++ ) sum[i] = sum[i - 1] + E[i];
}
int main(){
    initEP(10000000);
    cin>>N;

    ll ans = 0,cnt = 0;
    for(int i = 0;i<tail && P[i]<=N;i++){
        cnt++;
        ans += sum[N/P[i]];
    }
    cout<<ans*2-cnt<<endl;


    return 0;
}