Acwing220：最大公约数

题意：

• 求$\sum_{i=1}^N\sum_{j=1}^Ngcd(i,j)$为素数的有多少对。

思路：

莫比乌斯反演是肯定能做的。
考虑别的思路。
首先常规套路枚举$gcd=d$。
当然这里的$d$为素数。
$$ \sum_{d=1}^N\sum_{i=1}^N\sum_{j=1}^N[gcd(i,j)=d] $$
提出$d$。
$$ \sum_{d=1}^N\sum_{i=1}^{\frac{N}{d}}\sum_{j=1}^\frac{N}{d}[gcd(i,j)=1] $$
后面这个式子就很熟悉了。
$$ \sum_{d=1}^N\sum_{i=1}^\frac{N}{d}2\varphi(i)-1 $$
设$f(i)=\sum_1^i\varphi(i)$。
原式有
$$ \sum_{d=1}(2*f(\frac{n}{d})-1) $$
所以$O(n)$预处理$\varphi$前缀和后线性求和就行。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e7 + 10;
ll phi[maxn], ans;
int primes[maxn], cnt;
bool vis[maxn];
void init(int n)
{
    phi[1] = 1;
    for(int i = 2; i <= n; i++)
    {
        if(!vis[i])
        {
            primes[++cnt] = i;
            phi[i] = i-1;
        }
        for(int j = 1; primes[j] <= n/i; j++)
        {
            vis[primes[j]*i] = 1;
            if(i % primes[j] == 0)
            {
                phi[primes[j]*i] = phi[i]*primes[j];
                break;
            }
            else phi[primes[j]*i] = phi[i]*(primes[j]-1);
        }
    }

    for(int i = 1; i <= n; i++)
        phi[i] = phi[i-1] + phi[i];
}
int n;
int main()
{
    init(1e7);
    scanf("%d", &n);
    for(int i = 1, d; i <= cnt; i++)
    {
        d = primes[i];
        if(d > n) break;
        ans += 2*phi[n/d]-1;
    }
    cout << ans << endl;    
    return 0;
}