[bzoj 2818] Gcd

给定正整数N, 求1≤x,y≤N且Gcd(x,y)为素数的数对(x,y)的对数. (1≤N≤10^7) 通常来讲, 枚举gcd是个不错的选择. 不妨先令x>y.

所以打一个素数表, 求欧拉函数函数前缀和-1即可 (扣除).

说一下线性筛怎么打欧拉函数表. 首先, 对素数, . 用最小质因子的倍数筛后面的, 分两类: 质因子和倍数互质, 由欧拉函数的积性, 乘起来就好; 不互质, 用公式 连乘积部分生成的数与倍数相同, 所以乘上质因子就好.

最后把答案乘2加1.

#include <bits/stdc++.h>
#define Rep(i,a,b) for (int i=(a), i##_=(b); i<i##_; ++i)
#define For(i,a,b) for (int i=(a), i##_=(b); i<=i##_; ++i)
#define Down(i,a,b) for (int i=(a), i##_=(b); i>=i##_; --i)
 
using namespace std;
typedef long long ll;
const int MAX_N = 1e7;
 
int prime[MAX_N], phi[MAX_N + 1], cnt;
ll sum[MAX_N + 1];
 
void sieve(int n)
{
    static bool f[MAX_N + 1];
    phi[1] = 1;
    For (i, 2, n) {
        if (!f[i]) {
            phi[i] = i-1;
            prime[cnt++] = i;
        }
        for (int j = 0; j < cnt && i * prime[j] <= n; ++j) {
            int k = i * prime[j];
            f[k] = true;
            if (i % prime[j] == 0) {
                phi[k] = phi[i] * prime[j];
                break;
            } else
                phi[k] = phi[i] * (prime[j]-1); 
        }
    }
}
 
ll gcd(ll a, ll b)
{
    return b ? gcd(b, a % b) : a;
}
 
int main()
{
    int n;
    scanf("%d", &n);
    sieve(n);
    // 1<=j<i gcd(j, i)=1
    For (i, 2, n) sum[i] = sum[i-1] + phi[i];
    ll ans = 0;
    Rep (i, 0, cnt)
        ans += 2*sum[n/prime[i]] + 1;
    printf("%lld\n", ans);
    return 0;
}