GESP 题解库 / 8 级题解 / [GESP202403 八级] 公倍数问题 · 第 18 / 24 题
GESP202403 八级 · P10263 · 中等

把"公倍数"化成各自整除 k

ans_k = (k 的不超过 N 的因子个数) × (k 的不超过 M 的因子个数),枚举倍数统计。

📐
N, M ≤ 10⁵
矩阵的行数与列数
🔢
K ≤ 10⁶
小朋友的编号上界
⚡
O((N + M) log K)
枚举倍数(调和级数)
🎯
因子计数 × 因子计数
核心公式
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

小 A 写了一个 N × M 的矩阵 A,我们看不到这个矩阵,但我们可以知道,其中第 i 行第 j 列的元素 A_{i,j} 是 i 和 j 的公倍数(i = 1, …, N,j = 1, …, M)。现在有 K 个小朋友,其中第 k 个小朋友想知道,矩阵 A 中最多有多少个元素可以是 k(k = 1, 2, …, K)。请你帮助这些小朋友求解。

注意:每位小朋友的答案互不相关。例如,有些位置既可能是 x,又可能是 y,则它同时可以满足 x, y 两名小朋友的要求。

方便起见,你只需要输出 Σ_{k=1}^{K} k × ans_k 即可,其中 ans_k 表示第 k 名小朋友感兴趣的答案。

输入格式:第一行三个正整数 N, M, K。

输出格式:输出一行,即 Σ_{k=1}^{K} k × ans_k。请注意,这个数可能很大,使用 C++ 语言的选手请酌情使用 long long 等数据类型存储答案。

输入输出样例

样例内容
输入 #12 5 2
输出 #19
输入 #2100 100 100
输出 #2185233
样例 1 解释只有 A_{1,1} 可以是 1,其余都不行;A_{1,1}, A_{1,2}, A_{2,1}, A_{2,2} 都可以是 2,而其余不行。因此答案是 1 × 1 + 2 × 4 = 9
💡
人话翻译:矩阵看不见,但每个格子 (i, j) 有一个"能填哪些数"的许可证:只要是 i 和 j 的公倍数就能填。
于是"位置 (i, j) 可以等于 k"就等价于"k 同时是 i 和 j 的公倍数",也就是 i | k 且 j | k。
这一转化特别关键:它把 i 和 j 拆开了——行只需要满足"i 是 k 的因子且 i ≤ N",列只需要满足"j 是 k 的因子且 j ≤ M"。
两件事互不影响,所以由乘法原理:ans_k = (k 的 ≤ N 的因子个数) × (k 的 ≤ M 的因子个数)。
剩下的问题就是:怎么快速数出"每个 k 有多少个不超过 N 的因子"。答案是枚举倍数:对每个 i,把 i, 2i, 3i, … 都 +1。

🔍 关键词提取

公倍数化整除因子个数枚举倍数调和级数乘法原理long long

已知条件

项目说明
输入一行三个正整数 N, M, K
输出一行:Σ_{k=1}^{K} k × ans_k(无取模)
ans_k 含义矩阵中最多有多少个位置可以等于 k
数据范围N, M ≤ 10⁵,K ≤ 10⁶
部分分30%:N, M, K ≤ 10;60%:N, M, K ≤ 500
答案量级实测 N = M = 10⁵、K = 10⁶ 时为 184787888124744 ≈ 1.85 × 10¹⁴
时限1 秒 / 256 MB

需要解决的问题

02
思维导图
整理解题思路的全貌
📐 i | k 且 j | k ⟹ ans_k = cntN[k] × cntM[k]
🧠 条件化简
A_{i,j} 是 i 与 j 的公倍数
(i, j) 可以等于 k ⟺ k 是 i、j 的公倍数
⟺ lcm(i, j) | k
⟺ i | k 且 j | k(解耦的关键一步)
🔢 计数公式
ans_k = (#i ≤ N 且 i | k) × (#j ≤ M 且 j | k)
cntN[k] 就是"k 的不超过 N 的因子个数"
行与列独立 ⟹ 乘法原理
不同 k 的答案互不相关,可各算各的
⚙️ 实现
开 cntN[1…K]、cntM[1…K]
i = 1 … min(N, K):把 i, 2i, 3i, … ≤ K 的倍数 +1
j = 1 … min(M, K):同样处理 cntM
Σ k × cntN[k] × cntM[k] 输出(long long)
⚠️ 易错点
数组只开到 K 而不是 K + 1
外层上界忘写 min(N, K)
只数一遍因子再平方(两维上界不同)
用 int 存答案(1.85 × 10¹⁴ 溢出)
03
样例手算推导
两份样例手算 + 调和级数复杂度

🧮 样例手算:N = 2, M = 5, K = 2 与 N = M = K = 100

先看小样例。条件"(i, j) 可以是 k"拆成两半:i ≤ N 且 i | k;j ≤ M 且 j | k。

k可以是 k 的行号 i可以是 k 的列号 jans_kk × ans_k
1i ≤ 2 且 i | 1 ⟹ {1}j ≤ 5 且 j | 1 ⟹ {1}1 × 1 = 11
2i ≤ 2 且 i | 2 ⟹ {1, 2}j ≤ 5 且 j | 2 ⟹ {1, 2}2 × 2 = 48
合计———9
1
再用"枚举倍数"的视角跑一遍

cntN:i = 1 时给 cntN[1]、cntN[2] 各 +1;i = 2 时给 cntN[2] +1

于是 cntN[1] = 1、cntN[2] = 2

cntM:j = 1 时给 cntM[1]、cntM[2] +1;j = 2 时给 cntM[2] +1;j = 3、4、5 的倍数都超过 K = 2,跳过

于是 cntM[1] = 1、cntM[2] = 2

求和:1 × 1 × 1 + 2 × 2 × 2 = 1 + 8 = 9

✅ 9,与样例输出一致

2
与题面样例解释逐个位置对照

k = 1:只有 (1, 1) 一个位置 ⟹ ans₁ = 1

k = 2:(i, j) ∈ {1, 2} × {1, 2},共 4 个位置 ⟹ ans₂ = 4

题面说"A_{1,1} 可以是 1,其余都不行"

题面说"A_{1,1}, A_{1,2}, A_{2,1}, A_{2,2} 都可以是 2"

两句话与我们的公式完全吻合

✅ 公式得到验证

3
再看 N = M = K = 100 的样例

答案 185233 用同一套公式算出来(程序验证)

抽查 k = 1:cntN = cntM = 1 ⟹ ans₁ = 1,贡献 1

抽查 k = 97(质数):因子只有 1 与 97,均 ≤ 100,故 cntN = cntM = 2 ⟹ ans₉₇ = 4,贡献 388

抽查 k = 100:因子共 9 个(1, 2, 4, 5, 10, 20, 25, 50, 100),全部 ≤ 100 ⟹ ans₁₀₀ = 9 × 9 = 81,贡献 8100

✅ 185233(与样例 2 一致)

🔑
为什么"最多有多少个位置可以等于 k"就是"这些位置全都能同时取 k"?
因为题目明确说了每位小朋友的答案互不相关:同一个位置可以同时"有可能等于 x"和"有可能等于 y"。所以我们只需要数"有多少个位置满足条件",不需要担心这些位置能不能在同一个矩阵里同时取到 k。
每个格子的取值本来就是"任选一个公倍数",只要 k 是许可的公倍数,它就可以取 k。

🧮 为什么用"枚举倍数"这么快 —— 调和级数

目标:为所有 k ≤ K 求出"k 的不超过 N 的因子个数"。

做法枚举对象工作量能否通过
枚举倍数(推荐)i = 1 … min(N, K),把 i 的每个倍数 +1Σ ⌊K / i⌋ ≈ 1.2 × 10⁷可以
对每个 k 试除找因子k = 1 … K,各试到 √k≈ 10⁹超时
枚举所有位置 (i, j)N × M 个格子≤ 10¹⁰超时
1
第 1 步:把"因子"换成"倍数"

想数 cntN[k] = #{ i ≤ min(N, K) : i | k }

直接对每个 k 找因子,就要枚举 √k 个候选

反过来想:i | k ⟺ k 是 i 的倍数

"把所有 ≤ K 的 i 的倍数捡出来"就等于"为每个 k 累加它的因子"

两者是同一件事的两种视角

✅ 视角一换,枚举对象从 k 变成 i

2
第 2 步:算一算总量(调和级数)

i = 1 时贡献 K 次,i = 2 时贡献 K/2 次,i = 3 时 K/3 次 …

总计 Σ_{i=1}^{min(N,K)} ⌊K / i⌋ ≈ K × ln(min(N, K))

K = 10⁶、min(N, K) = 10⁵:

10⁶ × (1 + 1/2 + … + 1/10⁵) ≈ 10⁶ × 12.09 ≈ 1.2 × 10⁷

N、M 两条循环加起来约 2.4 × 10⁷

✅ 只有两千万次加法,非常轻松

3
第 3 步:最后的求和与类型选择

ans = Σ_{k=1}^{K} k × cntN[k] × cntM[k]

cntN[k]、cntM[k] 都是 int,但乘积可能很大

k ≤ 10⁶、cnt 之后相乘 → 单项可达 10¹² 级,累加后达 1.85 × 10¹⁴

int 上限约 2.1 × 10⁹,必然溢出

所以写 1LL * k * cntN[k] * cntM[k],用 long long 累加

✅ long long:最大约 1.85 × 10¹⁴

⚠️
三个坑:
· cntN 与 cntM 必须分别统计,上界一个是 N、一个是 M,不能只数一遍再平方;
· 外层循环要写 i ≤ min(N, K),当 K 比 N 小时 i 超过 K 根本没倍数可加,白跑;
· 数组要开 K + 1 而不是 K,并注意累加式里先转 long long。
04
解法对比
枚举倍数 + 因子计数 vs 逐位置枚举 / 逐个 k 试除

⚔️ 解法对比

🟢 枚举倍数 + 因子计数(推荐) 推荐

cntN、cntM 各用一次"枚举 i 的所有倍数"求出,再 Σ k × cntN[k] × cntM[k]

  • 时间 O((N + M) log K) ≈ 2.4 × 10⁷
  • 空间 O(K)(两个 int 数组)
  • 代码约 15 行
  • 不需要任何数论预处理
💡
为什么快:把"数因子"换成"贴倍数",总工作量就变成Σ_{i=1}^{min(N,K)} ⌊K / i⌋ ≈ K ln min(N, K),这是调和级数级复杂度,比 O(K √K) 的试除法快两个数量级。

🟠 枚举所有位置 (i, j) 并算 lcm

对每个格子算出 lcm(i, j),再把它的所有 ≤ K 的倍数计数 +1

  • 时间 O(N × M) = 10¹⁰,必然超时
  • 代码最短,最贴近题面字面
  • 只够 30 分(N, M, K ≤ 10)
  • lcm 还可能溢出 int
⚠️
它为什么会超时:N 与 M 都到 10⁵ 时格子有 10¹⁰ 个,无论怎么优化都做不到 1 秒。
正确做法是不枚举格子,只枚举下标:把"两个下标"的条件拆成两份独立的因子计数。

📈 性能对比

方案复杂度结论
枚举倍数(推荐)O((N + M) log K) ≈ 2.4 × 10⁷✅ 满分
枚举全部位置 (i, j) 求 lcmO(N · M) ≤ 10¹⁰❌ 只够 30 分
对每个 k 试除求因子数O(K √K) ≈ 10⁹❌ 超时
05
算法流程图
枚举倍数统计因子数的主流程
开始读入 N、M、K,开 cntN[1…K]、cntM[1…K] 并清零枚举 i = 1 … min(N, K):把 cntN 中 i 的所有倍数 +1枚举 j = 1 … min(M, K):把 cntM 中 j 的所有倍数 +1ans = 0,开始遍历 k = 1 … K把 k × cntN[k] × cntM[k] 累加进 ans(long long)k 已经到了 K 吗?是 ✓输出 ans否 ✗k += 1,回到上一步继续累加输出 ans(Σ k × ans_k)k += 1
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

📐 公倍数问题计算器

输入一行三个整数 N M K(演示版 N, M ≤ 10⁵、K ≤ 10⁶)。程序会枚举倍数统计 cntN、cntM,并给出 Σ k × ans_k;K ≤ 40 时逐行列出每个 k 的明细。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码(枚举倍数 + long long 累加)

#include <bits/stdc++.h>
using namespace std;

int cntN[1000005];      // cntN[k] = k 的不超过 N 的正因子个数
int cntM[1000005];      // cntM[k] = k 的不超过 M 的正因子个数

int main() {
    int N, M, K;
    scanf("%d %d %d", &N, &M, &K);

    // "i 是 k 的因子" ⟺ "k 是 i 的倍数":反过来贴倍数即可
    for (int i = 1; i <= min(N, K); i++)
        for (int k = i; k <= K; k += i)
            cntN[k]++;                 // i 的所有 ≤ K 的倍数各 +1

    for (int j = 1; j <= min(M, K); j++)
        for (int k = j; k <= K; k += j)
            cntM[k]++;

    long long ans = 0;
    for (int k = 1; k <= K; k++)
        ans += 1LL * k * cntN[k] * cntM[k];   // 先转 long long 再乘

    printf("%lld\n", ans);
    return 0;
}
🔑
三个要点:① 两个数组分别统计:一个是"因子 ≤ N"、一个是"因子 ≤ M",上界不同;② 外层循环写成 i ≤ min(N, K),避免 i > K 时白跑;③ 累加式写成 1LL * k * cntN[k] * cntM[k],否则三个 int 先相乘就溢出了。

📖 关键几行怎么看

代码作用为什么这样写
for (int k = i; k <= K; k += i)贴倍数把"因子视角"换成"倍数视角"
cntN[k]++;给因子个数 +1i 恰好是 k 的一个 ≤ N 的因子
i <= min(N, K)外层上界i > K 时没有倍数可贴
cntM[k]++;第二维独立统计行、列的可用数互不影响
ans += 1LL * k * cntN[k] * cntM[k];累加乘之前先转 long long,防溢出
printf("%lld\n", ans);输出答案是 long long
⚠️
五个坑:① 数组只开到 K(要 K + 1);② 外层循环忘写 min(N, K),K 小时白跑很多次;③ 只统计一遍因子个数再平方(两维上界一个是 N 一个是 M);④ ans 用 int(最大 1.85 × 10¹⁴,必溢出);⑤ 把 ans_k 理解成"k 必须是最小公倍数"——其实只要 k 是公倍数就能填,"最小"这个限制并不存在。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
2 5 29题面样例 1:ans₁ = 1、ans₂ = 4,1 + 8 = 9
100 100 100185233题面样例 2:中等规模,验证公式与求和
1 1 11最小规模:只有 (1, 1) 一个格子,且只能填 1
1 1 621N = M = 1 时 ans_k 恒为 1,答案就是 1 + 2 + … + 6
2 3 672两维上界不同的小数据,逐 k 核对 cntN、cntM
100000 100000 1000000184787888124744极限数据:答案约 1.85 × 10¹⁴,必须 long long
✅
自查清单:① 有没有把条件化简成 i | k 且 j | k?② 两个数组分别统计了吗?③ 外层上界写 min(N, K) / min(M, K) 了吗?④ 答案用了 long long 吗?

🚨 易错点清单

⚠️
数组开小:cntN、cntM 要开到 K + 1,因为下标最大取到 K。
⚠️
外层上界写错:必须是 min(N, K)(M 侧同理),否则 i > K 时白跑一整个循环。
⚠️
少统计一遍:cntN 与 cntM 的上界分别是 N 与 M,不能只算一遍再平方。
⚠️
int 溢出:答案最大约 1.85 × 10¹⁴,累加时要写 1LL * k * cntN[k] * cntM[k]。
⚠️
概念错位:位置 (i, j) 只要满足 "k 是 i、j 的公倍数"就可以填 k,不要求它是"最小的"公倍数。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O((N + M) log K)
空间复杂度
O(K)
枚举倍数次数
约 2.4 × 10⁷
答案量级
≤ 约 1.85 × 10¹⁴

时间怎么算的?

空间都用在哪?

两个 int 数组,长度都是 K + 1,共 2 × 4 MB = 8 MB;其余变量都是常数级。远低于 256 MB 的限制。

✅ 两千万次加法在 1 秒内非常轻松,这就是"调和级数"级复杂度的威力。唯一必须留心的是答案类型:最大约 1.85 × 10¹⁴,超过 int 四个数量级,必须用 long long 存 ans,并在乘法前先转型。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// ① 数"k 的不超过 N 的正因子个数":枚举 i 的所有倍数
int cnt[K + 1] = {0};
for (int i = 1; i <= min(N, K); i++)      // 因子 i 必然 ≤ min(N, K)
    for (int k = i; k <= K; k += i) cnt[k]++;   // 贴 i, 2i, 3i, …

// 复杂度:Σ_{i=1}^{min(N,K)} ⌊K / i⌋ ≈ K · ln(min(N, K)),调和级数级

// ② 条件化简的通用套路(本题最关键的一步)
//    "k 是 i 与 j 的公倍数"
//    ⟺ i | k 且 j | k            ← 把 i、j 拆开,能分别统计
//    ⟺ lcm(i, j) | k             ← 等价,但两维耦合,不好统计

// ③ 乘法原理:两维独立就把"数对"变成"两次数数再相乘"
//    ans_k = cntN[k] * cntM[k]

// ④ 溢出意识
long long ans = 0;
ans += 1LL * k * cntN[k] * cntM[k];    // 三个 int 相乘前先转 long long

// ⑤ 同类场景
//    · 统计 gcd(i, j) = d 的数对:用 cnt[d] 及倍数的容斥
//    · 求 Σ_{k=1}^{K} d(k)(因子个数和):同样是"贴倍数"直接秒
//    · 埃氏筛求质因子表:也是 i 的所有倍数 +1 的同一套路

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
枚举倍数(调和级数)数每个 k 的不超过 N 的因子个数约数计数、gcd 倍数容斥、埃氏筛类预处理
条件化简把 lcm(i,j) | k 换成 i | k 且 j | k任何"两个量的耦合条件"拆成独立条件的题
乘法原理可选行数 × 可选列数两维 / 多维独立的计数问题
类型估算先估答案 1.85 × 10¹⁴,再决定用 long long所有"答案可能很大"的计数题
🌟
思考题:如果矩阵再加一个维度(N × M × L 的立方体,A_{i,j,p} 是 i, j, p 的公倍数),公式要怎么改、答案要用什么类型?(提示:三个维度互相独立,所以 ans_k = cntN[k] × cntM[k] × cntL[k],只要再乘一项、再贴一层倍数即可;但答案量级会进一步变大,稳妥起见应改用 __int128 或高精度——这也是"先估量级,再选类型"的一次很好的训练。)