[数据结构与算法]最大公约数Ⅱ（欧拉函数）

最大公约数

求GCD(x,y) 为素数的数对 (x,y) 有多少对。

关键：将x y 拆成 a * d，b * d，(d为素数)、前缀和优化、phi[1]的另外处理.

题解转自秦大佬题解。

代码：

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

const int N = 10000010;

ll prime[N],phi[N],n,idx,sum[N],ans;
bool st[N];

void get_phi(int n)//欧拉函数之和
{
    phi[1] = 1;
    for(int i = 2; i <= n; i ++ )
    {
        if(!st[i])
        {
            prime[idx ++ ] = i;
            phi[i] = i - 1;
        }
        
        for(int j = 0; i * prime[j] <= n; j ++ )
        {
            st[prime[j] * i] = true;
            if(i % prime[j] == 0)
            {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        }
    }
}

int main()
{
    cin>>n;
    
    get_phi(n);
    
    for(int i = 2; i <= n; i ++ )//前缀和优化，1另外处理
    sum[i] = sum[i - 1] + phi[i];
    
    for(int i = 0; i < idx; i ++ )
    {
        int k = n / prime[i];
        ans += sum[k] * 2 + 1;//1 x y没有差别不用乘2
    }
    
    cout<<ans;
    return 0;
}