基础数学算法-最大公约数

题目-最大公约数

问题分析

因为数据范围很大$10^7$, 只能用线性的做法
假设$\gcd (a,b)=p$, $p$是质数, 枚举$1\sim n$中所有的质数, 因为$\gcd (a,b)=p$

因此有
$$\gcd (\frac{a}{p},\frac{b}{p})=1$$
等价于统计有多少个
$$1\le \frac{a}{p}\le \frac{b}{p}\le \frac{N}{p}$$
两个数互质的数对的个数

算法步骤

• 首先线性筛法预处理质数和欧拉函数
• 然后枚举所有的质数, $t=\frac{N}{p}$, 累计$\varphi (t)$

算法时间复杂度$O(n)$

代码实现

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 1e7 + 10;

int n;
int primes[N];
LL phi[N];
int cnt;
bool st[N];

void init(int n) {
   
    phi[1] = 1;
    for (int i = 2; i <= n; ++i) {
   
        if (!st[i]) {
   
            primes[cnt++] = i;
            phi[i] = i - 1;
        }

        for (int j = 0; primes[j] <= n / i; ++j) {
   
            st[i * primes[j]] = true;
            if (i % primes[j]) {
   
                phi[i * primes[j]] = phi[i] * (primes[j] - 1);
            }
            else {
   
                phi[i * primes[j]] = phi[i] * primes[j];
                break;
            }
        }
    }

    for (int i = 1; i <= n; ++i) phi[i] += phi[i - 1];
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    init(n);

    LL ans = 0;
    for (int i = 0; i < cnt; ++i) {
   
        int t = n / primes[i];
        ans += 2 * (phi[t] - phi[0]) - 1;
    }

    cout << ans << '\n';

    return 0;
}