这是一个功能完备的 C++ 数据生成器。它集成了调和级数预处理的标准解法（用于生成 .out）和针对不同数据范围的参数构造逻辑（用于生成 .in）。

运行此代码将自动在当前目录下生成 1.in/1.out 到 10.in/10.out。

数据生成策略

• Case 1-3 (30% 数据):
  • Case 1: 极小边界值 $N=1, M=1, K=1$。
  • Case 2: 样例 1 的类似数据。
  • Case 3: $N, M, K$ 在 10 以内的随机数据。
• Case 4-5 (60% 数据):
  • Case 4: $N, M, K$ 在 100 左右。
  • Case 5: 边界测试 $N=M=K=500$。
• Case 6-10 (100% 数据):
  • Case 6: $N, M$ 极大 ($10^5$)，但 $K$ 较小 ($100$)。测试当 $K$ 限制了计算范围时的正确性。
  • Case 7: $N, M$ 较小 ($10$)，但 $K$ 极大 ($10^6$)。测试当 $N, M$ 限制了因子范围时的正确性。
  • Case 8: $N$ 极大，$M$ 极小 ($1$)，$K$ 极大。测试不对称数据。
  • Case 9: 综合大数据，接近上限 ($N, M \approx 5 \times 10^4, K \approx 5 \times 10^5$)。
  • Case 10: 极限数据，达到题目上限 ($N=M=10^5, K=10^6$)，压力测试。

C++ 数据生成器代码

/**
 * P10263 [GESP202403 八级] 公倍数问题 - 数据生成器
 * 功能：生成 1.in/1.out ~ 10.in/10.out
 */

#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <vector>
#include <random>
#include <ctime>
#include <cstring>

using namespace std;

// ==========================================
// Part 1: 标准题解逻辑 (用于生成 .out)
// ==========================================
namespace Solution {
    const int MAXK = 1000005;
    // 定义在全局以避免栈溢出，每次求解前需清空
    int cntN[MAXK];
    int cntM[MAXK];

    long long solve(int N, int M, int K) {
        // 清空计数数组，只清空用到 K 的部分即可
        // 使用 memset 更快，但注意 K 可能变小，所以这里按 K 循环清空或直接 memset 全局
        // 为了安全起见，这里循环清空 1~K
        for(int i = 1; i <= K; i++) {
            cntN[i] = 0;
            cntM[i] = 0;
        }

        // 1. 计算 cntN
        // 遍历因子 i，直到 min(N, K)
        int limit_n = min(N, K);
        for (int i = 1; i <= limit_n; i++) {
            for (int j = i; j <= K; j += i) {
                cntN[j]++;
            }
        }

        // 2. 计算 cntM
        int limit_m = min(M, K);
        for (int i = 1; i <= limit_m; i++) {
            for (int j = i; j <= K; j += i) {
                cntM[j]++;
            }
        }

        // 3. 统计答案
        long long total_ans = 0;
        for (int k = 1; k <= K; k++) {
            long long ans_k = (long long)cntN[k] * cntM[k];
            total_ans += k * ans_k;
        }

        return total_ans;
    }
}

// ==========================================
// Part 2: 数据构造工具
// ==========================================
mt19937 rng((unsigned)time(0));

int randInt(int min, int max) {
    return uniform_int_distribution<int>(min, max)(rng);
}

// ==========================================
// Part 3: 测试点生成逻辑
// ==========================================
void makeData(int id) {
    string inName = to_string(id) + ".in";
    string outName = to_string(id) + ".out";
    ofstream fin(inName);
    ofstream fout(outName);

    int N, M, K;

    // 根据 id 构造不同强度的数据
    if (id == 1) {
        // 极小边界
        N = 1; M = 1; K = 1;
    } 
    else if (id == 2) {
        // 类似样例 1
        N = 2; M = 5; K = 2;
    } 
    else if (id == 3) {
        // 30% 数据范围
        N = randInt(5, 10);
        M = randInt(5, 10);
        K = randInt(5, 10);
    } 
    else if (id == 4) {
        // 60% 数据范围 - 中等
        N = randInt(50, 100);
        M = randInt(50, 100);
        K = randInt(50, 100);
    } 
    else if (id == 5) {
        // 60% 数据范围 - 边界
        N = 500; M = 500; K = 500;
    } 
    else if (id == 6) {
        // N, M 很大，K 很小
        // 测试优化逻辑：limit = min(N, K)
        N = 100000; M = 100000; K = 100;
    } 
    else if (id == 7) {
        // N, M 很小，K 很大
        // 测试优化逻辑：只遍历到 min(N, K)
        N = 10; M = 10; K = 1000000;
    } 
    else if (id == 8) {
        // 极端不对称
        N = 100000; M = 1; K = 1000000;
    } 
    else if (id == 9) {
        // 100% 数据 - 较大随机
        N = randInt(40000, 50000);
        M = randInt(40000, 50000);
        K = randInt(400000, 500000);
    } 
    else { // id == 10
        // 100% 数据 - 极限压力测试
        N = 100000; M = 100000; K = 1000000;
    }

    // 写入输入文件
    fin << N << " " << M << " " << K << endl;

    // 计算并写入输出文件
    fout << Solution::solve(N, M, K) << endl;

    fin.close();
    fout.close();

    cout << "Generated Case " << id << ": N=" << N << " M=" << M << " K=" << K << endl;
}

int main() {
    // 提升 I/O 效率
    ios::sync_with_stdio(false);
    cin.tie(0);

    for (int i = 1; i <= 10; i++) {
        makeData(i);
    }

    cout << "All data generated successfully." << endl;
    return 0;
}

使用指南

1. 保存：将代码保存为 generator.cpp。
2. 编译：使用 g++ generator.cpp -o generator -O2 进行编译。
3. 运行：执行 ./generator (或 generator.exe)。
4. 结果：程序会在当前目录下生成 1.in~10.in 和 1.out~10.out。
   • Case 10 运行时间可能会稍长（约 0.1~0.2 秒），因为 $K=10^6$，这是正常的。
   • 生成的数据覆盖了题目中 30%, 60%, 100% 的所有数据范围要求，以及 $N \gg K$ 和 $K \gg N$ 等边界情况。

你好！这是 GESP 2024年3月八级真题《公倍数问题》的题解。

题目分析

题目问的是：对于每个 $k \in [1, K]$，矩阵中满足“$k$ 是 $i$ 和 $j$ 的公倍数”的坐标 $(i, j)$ 有多少个。 数学条件转化：

1. 题目条件：$A_{i,j}$ 是 $i$ 和 $j$ 的公倍数。
2. 询问：$A_{i,j}$ 可以是 $k$ 的数量。这意味着 $k$ 必须满足题目对 $A_{i,j}$ 的定义。
3. 即：$k$ 必须是 $i$ 和 $j$ 的公倍数。
4. 这等价于：$i$ 是 $k$ 的因子 且 $j$ 是 $k$ 的因子。

设 $d_N(k)$ 为 $[1, N]$ 中能整除 $k$ 的数的个数，$d_M(k)$ 为 $[1, M]$ 中能整除 $k$ 的数的个数。 则对于特定的 $k$，满足条件的坐标数量 $\text{ans}_k = d_N(k) \times d_M(k)$。 最终要求的答案是 $\sum_{k=1}^{K} k \times \text{ans}_k$。

核心算法

利用调和级数的性质进行预处理。 我们不枚举 $k$ 去分解因子（那样太慢），而是枚举因子 $i$，将 $i$ 的贡献累加到它的所有倍数 $k$ 上。这类似于“埃氏筛”的思想。

标准代码 (C++14)

/**
 * 题目：P10263 [GESP202403 八级] 公倍数问题
 * 算法：数论 / 调和级数枚举 / 贡献法
 * 时间复杂度：O(K log K + K log N + K log M) -> 实际上是 O(K log K) 级别
 * 空间复杂度：O(K)
 */

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 建议开启 O2 优化（在部分 OJ 或比赛环境中默认开启，本地可手动开启）
// #pragma GCC optimize(2)

// 定义最大范围，K 最大 10^6
const int MAXK = 1000005;

// cntN[k] 表示在 1~N 范围内，有多少个数是 k 的因子
// cntM[k] 表示在 1~M 范围内，有多少个数是 k 的因子
// 虽然计数用 int 足够（最大因子数也就几百），但为了避免计算乘积溢出，也可以直接用 long long
// 考虑到空间和缓存，这里用 int，计算时转 long long
int cntN[MAXK];
int cntM[MAXK];

void solve() {
    int N, M, K;
    if (!(cin >> N >> M >> K)) return;

    // 关键点1：贡献法统计因子个数
    // 我们不针对每个 k 去找因子，而是遍历因子 i，去找它是哪些 k 的因子。
    // 这样做利用了调和级数的性质，复杂度远优于暴力分解。
    
    // 1. 计算 cntN
    // 只需要遍历到 min(N, K)，因为 > K 的倍数不需要统计，> N 的因子不符合题目要求(i<=N)
    int limit_n = min(N, K);
    for (int i = 1; i <= limit_n; i++) {
        // 枚举 i 的倍数：i, 2i, 3i ... 直到 K
        for (int j = i; j <= K; j += i) {
            cntN[j]++;
        }
    }

    // 2. 计算 cntM
    // 同理，遍历到 min(M, K)
    int limit_m = min(M, K);
    for (int i = 1; i <= limit_m; i++) {
        for (int j = i; j <= K; j += i) {
            cntM[j]++;
        }
    }

    long long total_ans = 0;

    // 3. 统计最终答案
    for (int k = 1; k <= K; k++) {
        // 关键点2：数据溢出风险
        // k <= 10^6
        // cntN[k] 和 cntM[k] 最大约为 240 (10^6内因子最多的数)
        // 单项 ans_k ≈ 240 * 240 ≈ 5.7e4
        // k * ans_k ≈ 5.7e10，这已经超过了 int (2e9) 的范围
        // 累加和更是会达到 10^16 级别，必须使用 long long
        long long ans_k = (long long)cntN[k] * cntM[k];
        total_ans += k * ans_k;
    }

    cout << total_ans << endl;
}

int main() {
    // 竞赛标准 IO 优化
    ios::sync_with_stdio(false);
    cin.tie(0);

    solve();

    return 0;
}

---

时间和空间复杂度分析

1. 时间复杂度分析

算法的核心在于两个嵌套循环，形如：

for (int i = 1; i <= N; i++) {
    for (int j = i; j <= K; j += i) { ... }
}

内层循环执行次数为 $\lfloor \frac{K}{i} \rfloor$。 总运算次数约为：

$$\sum_{i=1}^{\min(N, K)} \frac{K}{i} + \sum_{i=1}^{\min(M, K)} \frac{K}{i} $$

根据调和级数近似公式 $\sum_{i=1}^{n} \frac{1}{i} \approx \ln n$，总复杂度约为：

$$O(K \ln (\min(N, K)) + K \ln (\min(M, K)))$$

由于 $N, M \le 10^5, K \le 10^6$，我们可以粗略认为复杂度上限是 $O(K \ln K)$。 代入数据：$10^6 \times \ln(10^5) \approx 10^6 \times 11.5 \approx 1.15 \times 10^7$ 次运算。 在 C++ 中，1秒通常能处理 $10^8$ 次运算(1GHz的CPU频率)，因此该算法非常高效，运行时间在 0.2s 以内。

2. 空间复杂度分析

我们需要两个长度为 $K$ 的数组 cntN 和 cntM。

• 空间：$2 \times 10^6 \times 4 \text{ Bytes} \approx 8 \text{ MB}$。
• 题目通常给 128MB 或 256MB，空间非常充裕。

3. 优化建议

当前的算法已经是最优解之一（接近线性）。

• 微小优化：如果 $N$ 和 $M$ 的值相同，可以只算一次 cntN，然后 cntM 直接复用（虽然对复杂度量级无影响）。
• IO优化：cin 和 cout 在数据量大时较慢，使用 ios::sync_with_stdio(false) 是必须的。
• 空间优化：如果 $K$ 极大导致空间不足，可以只开一个 cnt 数组。先算 cntN，计算完 $k$ 循环中的 ans_k 的一部分，清空数组，再算 cntM。但本题 $K=10^6$ 不需要这么做。

你好！我是你的OI教练。很高兴能为你讲解这道 GESP 八级的数论题目《公倍数问题》。

这道题目虽然是八级题，但核心在于数学推导和思维转换。只要把题目复杂的描述转化成数学公式，就会发现它其实是经典的“调和级数求和”模型。

我们拿出草稿纸，一起来拆解这道题。

1. 题目分析与思路推导

核心问题翻译

题目中说：$A_{i,j}$ 是 $i$ 和 $j$ 的公倍数。小朋友想知道矩阵中有多少个位置可以是 $k$。 这意味着我们要找满足以下条件的 $(i, j)$ 对的数量：

1. $A_{i,j}$ 可以取值为 $k$。
2. 即 $k$ 必须是 $i$ 和 $j$ 的公倍数。
3. 换句话说，$\text{lcm}(i, j) \mid k$（$k$ 能被 $\text{lcm}(i, j)$ 整除）。
4. 根据数学性质，$\text{lcm}(i, j) \mid k$ 等价于 $i \mid k$ 且 $j \mid k$（即 $i$ 是 $k$ 的因子，且 $j$ 是 $k$ 的因子）。

公式化

对于一个固定的 $k$，我们需要计算有多少对 $(i, j)$ 满足：

• $1 \le i \le N$ 且 $i \mid k$
• $1 \le j \le M$ 且 $j \mid k$

观察发现，$i$ 和 $j$ 的条件是独立的！ 令 $d_N(k)$ 表示在 $1$ 到 $N$ 范围内，$k$ 的因数个数。 令 $d_M(k)$ 表示在 $1$ 到 $M$ 范围内，$k$ 的因数个数。 那么对于 $k$，答案 $\texttt{ans}_k = d_N(k) \times d_M(k)$。

最终我们需要求：

$$\text{Total} = \sum_{k=1}^{K} (k \times d_N(k) \times d_M(k)) $$

2. 算法设计与优化

暴力做法（不可行）

如果对于每个 $k$，我们都去遍历 $1$ 到 $k$ 找因子：

• 单次查询复杂度 $O(k)$ 或 $O(\sqrt{k})$。
• 总复杂度 $O(K\sqrt{K})$，当 $K=10^6$ 时运算量约 $10^9$，会超时。

贡献法 / 筛法思想（正解）

我们可以反过来思考：不去枚举 $k$ 的因子，而是枚举因子 $i$，看看它是哪些 $k$ 的因子。

1. 定义两个数组 cntN[k] 和 cntM[k]，分别存储 $d_N(k)$ 和 $d_M(k)$。
2. 枚举因子 $i$：从 $1$ 遍历到 $\max(N, M)$。
3. 枚举倍数 $k$：对于每个 $i$，枚举它的倍数 $k = i, 2i, 3i, \dots$（直到 $K$）。
   • 如果 $i \le N$，说明 $i$ 是 $k$ 的一个合法因子（在 $N$ 范围内），cntN[k]++。
   • 如果 $i \le M$，说明 $i$ 是 $k$ 的一个合法因子（在 $M$ 范围内），cntM[k]++。
4. 最后遍历 $k$ 计算总和。

复杂度分析

这种“枚举倍数”的方法，总运算次数为：

$$\frac{K}{1} + \frac{K}{2} + \frac{K}{3} + \dots + \frac{K}{K} \approx K \times \ln K $$

这是著名的调和级数。 当 $K=10^6$ 时，$K \ln K \approx 10^6 \times 14 \approx 1.4 \times 10^7$。 这个计算量非常小，完全可以在 1 秒内通过。

3. C++ 标准代码 (NOIP C++14)

/**
 * 题目：P10263 [GESP202403 八级] 公倍数问题
 * 考点：数论、因子计数、调和级数复杂度分析
 * 时间复杂度：O(K log K)
 * 空间复杂度：O(K)
 */

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 数据范围 K <= 10^6，数组开稍微大一点
const int MAXK = 1000005;

// cntN[k] 存储 k 的因子中 <= N 的个数
// cntM[k] 存储 k 的因子中 <= M 的个数
// 使用 long long 防止乘积溢出（虽然单个计数很小，但为了保险）
long long cntN[MAXK];
long long cntM[MAXK];

int main() {
    // 1. IO 优化，处理大量数据时必备
    ios::sync_with_stdio(false);
    cin.tie(0);

    int N, M, K;
    if (!(cin >> N >> M >> K)) return 0;

    // 2. 预处理因子计数
    // 我们只需要枚举因子 i，直到 max(N, M)
    // 因为大于 max(N, M) 的数既不能贡献给 cntN 也就不能贡献给 cntM
    // 同时，我们只关心 <= K 的倍数
    int limit_i = max(N, M);

    for (int i = 1; i <= limit_i; i++) {
        // 判断当前因子 i 是否在 N 和 M 的范围内
        bool inN = (i <= N);
        bool inM = (i <= M);

        // 如果 i 既超过了 N 也超过了 M，其实 limit_i 已经限制住了，这里是双重保险
        if (!inN && !inM) continue;

        // 枚举 i 的倍数 k: i, 2i, 3i ... 直到 K
        // 这是调和级数复杂度的核心
        for (int k = i; k <= K; k += i) {
            if (inN) cntN[k]++;
            if (inM) cntM[k]++;
        }
    }

    // 3. 计算答案
    long long total_ans = 0;
    for (int k = 1; k <= K; k++) {
        // 第 k 个小朋友的答案 ans_k = cntN[k] * cntM[k]
        // 题目要求 sum(k * ans_k)
        
        // 注意数据范围：
        // ans_k 最大约为 240*240 (10^6内因子最多的数) ≈ 5.7e4
        // k * ans_k ≈ 10^6 * 5.7e4 ≈ 5.7e10
        // 累加和会达到 10^16 级别，必须使用 long long
        long long ans_k = cntN[k] * cntM[k];
        total_ans += k * ans_k;
    }

    cout << total_ans << endl;

    return 0;
}

4. 代码关键点与易错点注释

1. 数据类型：
   • 最终答案 total_ans 会达到 $10^{16}$ 数量级，超过 int ($2 \times 10^9$)，必须使用 long long。
2. 循环边界：
   • 外层循环 i 实际上只需要遍历到 max(N, M)，因为比 $N$ 和 $M$ 都大的因子对计数没有贡献。
   • 内层循环 k 必须遍历到 K，因为我们要计算所有小朋友的答案。
   • 内层循环的步长是 k += i，这是保证 $O(K \log K)$ 复杂度的关键，千万不要写成 $k++$。
3. 空间复杂度：
   • 我们开了两个 $10^6$ 的 long long 数组，大约占用 $16 \text{MB}$ 内存，远低于一般的 $128 \text{MB}$ 或 $256 \text{MB}$ 限制，非常安全。

5. 总结

这道题的关键在于意识到：计算 $k$ 有多少个因子在 $1 \dots N$ 之间，等价于枚举 $1 \dots N$ 之间的每个数，看它是哪些 $k$ 的因子。 这种“反向枚举”的思维方式在数论题目中非常常见（例如筛选法求素数），是八级选手必须掌握的技巧。