典.

user

1
2
3
4
5
6
7
8
9
10
11
最大公约数之和
令G(N)=\sum_{j=1}^N\sum_{i=1}^j\text{gcd}(i,j)。已知G(10)=122。

求G(10^{11})，并将你的答案对998244353取模。

我的思路:莫反.
给你一段相近的推导:

$$\begin{aligned}&\sum_{i=1}^n\sum_{j=1}^n\gcd(i,j)\\=&\sum_{i=1}^n\sum_{j=1}^n\sum_{d|\gcd(i,j)}\varphi(d)\\=&\sum_{i=1}^n\sum_{j=1}^n\sum_{d|i,j}\varphi(d)\\=&\sum_{d=1}^n\Big\lfloor\frac nd\Big\rfloor^2\varphi(d)\end{aligned}$$

请给我c++代码,注意取模.

Gemini

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
这是一个非常经典的数论问题。你的莫比乌斯反演推导非常正确，但在处理  时，由于求和区间是 ，我们需要对推导稍作调整。

### 推导过程

首先利用 ：


交换求和顺序，先枚举 ，再枚举 （必须是  的倍数），最后枚举 （必须是  的倍数且 ）：



由于 ，后面的双重求和即为等差数列求和：


最终公式为：


### 算法实现

对于 ，直接枚举  太慢。我们需要使用**杜教筛 (Du Sieve)** 来计算  的前缀和，并结合**数论分块 (Square Root Decomposition)** 来计算最终结果。

---

### C++ 代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

typedef long long ll;

const int MOD = 998244353;
const int INV2 = 499122177;
const int MAX_SIZE = 5000000; // 预处理范围，根据时限可调

int prime[MAX_SIZE / 10], cnt;
bool is_prime[MAX_SIZE];
int phi[MAX_SIZE];
ll sum_phi[MAX_SIZE];
unordered_map<ll, int> memo_phi;

// 预处理线性筛
void precompute() {
    fill(is_prime + 2, is_prime + MAX_SIZE, true);
    phi[1] = 1;
    for (int i = 2; i < MAX_SIZE; i++) {
        if (is_prime[i]) {
            prime[cnt++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; j < cnt && (ll)i * prime[j] < MAX_SIZE; j++) {
            is_prime[i * prime[j]] = false;
            if (i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        }
    }
    for (int i = 1; i < MAX_SIZE; i++) {
        sum_phi[i] = (sum_phi[i - 1] + phi[i]) % MOD;
    }
}

// 杜教筛计算 Phi 的前缀和
int get_sum_phi(ll n) {
    if (n < MAX_SIZE) return sum_phi[n];
    if (memo_phi.count(n)) return memo_phi[n];

    // Phi 的前缀和公式: S(n) = n*(n+1)/2 - sum_{i=2}^n S(n/i)
    ll res = (n % MOD) * ((n + 1) % MOD) % MOD * INV2 % MOD;
    for (ll l = 2, r; l <= n; l = r + 1) {
        r = n / (n / l);
        ll term = (r - l + 1) % MOD * get_sum_phi(n / l) % MOD;
        res = (res - term + MOD) % MOD;
    }
    return memo_phi[n] = (int)res;
}

int main() {
    ll N = 100000000000LL; // 10^11
    precompute();

    ll ans = 0;
    // 数论分块计算 sum phi(d) * f(N/d)
    for (ll l = 1, r; l <= N; l = r + 1) {
        r = N / (N / l);
        ll k = N / l;
        ll count_sum = (k % MOD) * ((k + 1) % MOD) % MOD * INV2 % MOD;
        
        ll phi_part = (get_sum_phi(r) - get_sum_phi(l - 1) + MOD) % MOD;
        ans = (ans + phi_part * count_sum) % MOD;
    }

    cout << ans << endl;
    return 0;
}

1
2
3
4
5
6
7
8
### 代码说明：

1. **预处理**：使用线性筛计算前  个  值。
2. **杜教筛**：核心逻辑是利用  递归求解，并用 `unordered_map` 记忆化。
3. **数论分块**：外层对  的公式进行分块，复杂度为 。
4. **取模注意**：在计算  时，由于  很大，先对  取模再乘法，或者使用  的逆元 `499122177`。

需要我帮你验证一下  的小样例结果吗？

fun fact

加上这道题一共过了322题,又爆了一道bonus,名为 contfrac .