ans_k = (k 的不超过 N 的因子个数) × (k 的不超过 M 的因子个数),枚举倍数统计。
小 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 等数据类型存储答案。
| 样例 | 内容 |
|---|---|
| 输入 #1 | 2 5 2 |
| 输出 #1 | 9 |
| 输入 #2 | 100 100 100 |
| 输出 #2 | 185233 |
| 样例 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 的因子个数)。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 |
(i, j) 可以是 k 的条件是什么?k 必须是 i 与 j 的公倍数。而"k 是 i、j 的公倍数"等价于"i | k 且 j | k",两个条件各自只涉及一个下标,这就是能高效统计的根本原因i | k 且 j | k"与"lcm(i, j) | k"等价?一方面 i | k 且 j | k 说明 k 是公倍数,而 lcm(i, j) 是最小公倍数,所以它一定整除 k;另一方面 i | lcm(i, j)、j | lcm(i, j),由整除的传递性反推也成立。两种写法等价,但"各自整除"这种更好用i ≤ N 且 i | k",列下标只需要满足"j ≤ M 且 j | k",两组约束完全独立,所以可用的位置数 = 可选行数 × 可选列数(乘法原理)k 的不超过 N 的因子个数"?反着来:i 是 k 的因子 ⟺ k 是 i 的倍数。所以对每个 i = 1 … min(N, K),把它的所有 ≤ K 的倍数 k 的计数 +1 即可。总次数是 Σ ⌊K / i⌋ ≈ K ln min(N, K)(调和级数级)1.85 × 10¹⁴,int 上限只有约 2.1 × 10⁹,所以 ans 与中间的乘积都必须用 long long(写 1LL * k * cntN[k] * cntM[k])先看小样例。条件"(i, j) 可以是 k"拆成两半:i ≤ N 且 i | k;j ≤ M 且 j | k。
| k | 可以是 k 的行号 i | 可以是 k 的列号 j | ans_k | k × ans_k |
|---|---|---|---|---|
| 1 | i ≤ 2 且 i | 1 ⟹ {1} | j ≤ 5 且 j | 1 ⟹ {1} | 1 × 1 = 1 | 1 |
| 2 | i ≤ 2 且 i | 2 ⟹ {1, 2} | j ≤ 5 且 j | 2 ⟹ {1, 2} | 2 × 2 = 4 | 8 |
| 合计 | — | — | — | 9 |
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,与样例输出一致
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"
两句话与我们的公式完全吻合
✅ 公式得到验证
答案 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 求出"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¹⁰ | 超时 |
想数 cntN[k] = #{ i ≤ min(N, K) : i | k }
直接对每个 k 找因子,就要枚举 √k 个候选
反过来想:i | k ⟺ k 是 i 的倍数
"把所有 ≤ K 的 i 的倍数捡出来"就等于"为每个 k 累加它的因子"
两者是同一件事的两种视角
✅ 视角一换,枚举对象从 k 变成 i
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⁷
✅ 只有两千万次加法,非常轻松
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。cntN、cntM 各用一次"枚举 i 的所有倍数"求出,再 Σ k × cntN[k] × cntM[k]
Σ_{i=1}^{min(N,K)} ⌊K / i⌋ ≈ K ln min(N, K),这是调和级数级复杂度,比 O(K √K) 的试除法快两个数量级。对每个格子算出 lcm(i, j),再把它的所有 ≤ K 的倍数计数 +1
N, M, K ≤ 10)lcm 还可能溢出 intN 与 M 都到 10⁵ 时格子有 10¹⁰ 个,无论怎么优化都做不到 1 秒。| 方案 | 复杂度 | 结论 |
|---|---|---|
| 枚举倍数(推荐) | O((N + M) log K) ≈ 2.4 × 10⁷ | ✅ 满分 |
| 枚举全部位置 (i, j) 求 lcm | O(N · M) ≤ 10¹⁰ | ❌ 只够 30 分 |
| 对每个 k 试除求因子数 | O(K √K) ≈ 10⁹ | ❌ 超时 |
输入一行三个整数 N M K(演示版 N, M ≤ 10⁵、K ≤ 10⁶)。程序会枚举倍数统计 cntN、cntM,并给出 Σ k × ans_k;K ≤ 40 时逐行列出每个 k 的明细。
点按钮开始 →
#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; }
i ≤ min(N, K),避免 i > K 时白跑;③ 累加式写成 1LL * k * cntN[k] * cntM[k],否则三个 int 先相乘就溢出了。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
for (int k = i; k <= K; k += i) | 贴倍数 | 把"因子视角"换成"倍数视角" |
cntN[k]++; | 给因子个数 +1 | i 恰好是 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 是公倍数就能填,"最小"这个限制并不存在。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
2 5 2 | 9 | 题面样例 1:ans₁ = 1、ans₂ = 4,1 + 8 = 9 |
100 100 100 | 185233 | 题面样例 2:中等规模,验证公式与求和 |
1 1 1 | 1 | 最小规模:只有 (1, 1) 一个格子,且只能填 1 |
1 1 6 | 21 | N = M = 1 时 ans_k 恒为 1,答案就是 1 + 2 + … + 6 |
2 3 6 | 72 | 两维上界不同的小数据,逐 k 核对 cntN、cntM |
100000 100000 1000000 | 184787888124744 | 极限数据:答案约 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,不能只算一遍再平方。1.85 × 10¹⁴,累加时要写 1LL * k * cntN[k] * cntM[k]。(i, j) 只要满足 "k 是 i、j 的公倍数"就可以填 k,不要求它是"最小的"公倍数。cntN:i 从 1 到 min(N, K),每次贴 ⌊K / i⌋ 个倍数,合计 ≈ K ln min(N, K)K = 10⁶、min(N, K) = 10⁵:10⁶ × 12.09 ≈ 1.2 × 10⁷cntM 同样约 1.2 × 10⁷O(K) = 10⁶2.4 × 10⁷ 次加法两个 int 数组,长度都是 K + 1,共 2 × 4 MB = 8 MB;其余变量都是常数级。远低于 256 MB 的限制。
✅ 两千万次加法在 1 秒内非常轻松,这就是"调和级数"级复杂度的威力。唯一必须留心的是答案类型:最大约 1.85 × 10¹⁴,超过 int 四个数量级,必须用 long long 存 ans,并在乘法前先转型。
// ① 数"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 或高精度——这也是"先估量级,再选类型"的一次很好的训练。)