ABC435B 不可整除区间
大约 5 分钟前缀和
ABC435B 不可整除区间
【算法标签】 前缀和、枚举
【语法标签】 :数组、for循环、前缀和
给定长度为 的正整数序列 。
求满足以下条件的整数对 ()的个数:
对于区间 内的每一个元素 , 都不是区间和 的约数。
换句话说:区间和不能被区间内任何一个元素整除。
数据范围:
二、解题思路
2.1 数据规模分析
是一个非常小的范围。我们来估算不同复杂度的运算量:
| 方法 | 复杂度 | 估算运算量 |
|---|---|---|
| 枚举所有区间 + 暴力求和 + 逐一检查 | ||
| 枚举所有区间 + 前缀和 + 逐一检查 | (常数更小) | |
| 枚举所有区间 + 暴力求和 + 逐一检查(优化 break) | 带剪枝 | 远小于 |
十万级别的运算量对于 C++ 来说完全是瞬间完成,所以直接三重循环枚举即可,不需要任何高级算法。
这就是 CSP-J 入门组题目的典型特征:数据范围小,考察的是对题意的理解和代码实现能力,而不是高深算法。
2.2 条件翻译
题目条件是:
对于所有 , 不是 的约数。
翻译成数学语言: 对所有 成立。
反过来想,什么时候区间不合法?只要存在一个 ,使得 ,这个区间就不算。
2.3 算法流程
- 用两层循环枚举所有区间 :
- 外层 从 到
- 内层 从 到
- 对于每个区间,先求出区间和
- 再遍历区间内每个元素 :
- 如果 ,说明这个区间不合法,直接跳过(break)
- 如果整个区间检查完都没有发现 ,答案 +1
2.4 前缀和优化(可选)
如果只是 ,直接每次暴力求和也没问题。但如果想写得更"竞赛",可以用前缀和把求区间和从 降到 ,整体从 降到 。
前缀和定义:,则区间和 。
例如 A = [8, 6, 10, 5, 7]
pre = [0, 8, 14, 24, 29, 36]
区间 [2, 4] 的和 = pre[4] - pre[1] = 29 - 8 = 21
验证:A2 + A3 + A4 = 6 + 10 + 5 = 21 ✓2.5 手动模拟样例
样例 1:
| 区间 [l,r] | 区间和 S | 检查过程 | 合法? |
|---|---|---|---|
| [1,1] | 8 | 8 % 8 = 0 | ❌ |
| [1,2] | 14 | 14%8=6≠0, 14%6=2≠0 | ✅ |
| [1,3] | 24 | 24%8=0 | ❌ |
| [1,4] | 29 | 29%8=5≠0, 29%6=5≠0, 29%10=9≠0, 29%5=4≠0 | ✅ |
| [1,5] | 36 | 36%6=0 | ❌ |
| [2,2] | 6 | 6%6=0 | ❌ |
| [2,3] | 16 | 16%6=4≠0, 16%10=6≠0 | ✅ |
| [2,4] | 21 | 21%6=3≠0, 21%10=1≠0, 21%5=1≠0 | ✅ |
| [2,5] | 28 | 28%6=4≠0, 28%10=8≠0, 28%5=3≠0, 28%7=0 | ❌ |
| [3,3] | 10 | 10%10=0 | ❌ |
| [3,4] | 15 | 15%10=5≠0, 15%5=0 | ❌ |
| [3,5] | 22 | 22%10=2≠0, 22%5=2≠0, 22%7=1≠0 | ✅ |
| [4,4] | 5 | 5%5=0 | ❌ |
| [4,5] | 12 | 12%5=2≠0, 12%7=5≠0 | ✅ |
| [5,5] | 7 | 7%7=0 | ❌ |
合法区间共 6 个,与样例输出一致。
样例 2:
任何区间的和都是区间长度,而区间内每个元素都是 1,任何数都能被 1 整除,所以必定存在 。答案为 0。
三、参考代码
版本一:暴力枚举(最直观)
#include <bits/stdc++.h>
using namespace std;
const int N = 55;
int a[N];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int ans = 0;
// 枚举区间左端点
for (int l = 1; l <= n; l++) {
// 枚举区间右端点
for (int r = l; r <= n; r++) {
// 暴力求区间和
int sum = 0;
for (int k = l; k <= r; k++) {
sum += a[k];
}
// 检查区间内每个元素是否都不是 sum 的约数
bool ok = true;
for (int k = l; k <= r; k++) {
if (sum % a[k] == 0) {
ok = false;
break;
}
}
if (ok) ans++;
}
}
cout << ans << endl;
return 0;
}版本二:前缀和优化(更竞赛风)
#include <bits/stdc++.h>
using namespace std;
const int N = 55;
int a[N];
int pre[N]; // pre[i] = a[1] + a[2] + ... + a[i]
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
pre[i] = pre[i - 1] + a[i];
}
int ans = 0;
for (int l = 1; l <= n; l++) {
for (int r = l; r <= n; r++) {
// O(1) 求区间和
int sum = pre[r] - pre[l - 1];
bool ok = true;
for (int k = l; k <= r; k++) {
if (sum % a[k] == 0) {
ok = false;
break;
}
}
if (ok) ans++;
}
}
cout << ans << endl;
return 0;
}四、复杂度分析
暴力版本(版本一)
- 枚举区间: 个区间
- 每个区间暴力求和:
- 每个区间逐一检查:
- 总复杂度:, 时约 次运算
前缀和版本(版本二)
- 枚举区间: 个区间
- 前缀和 O(1) 求区间和
- 每个区间逐一检查:
- 总复杂度:, 时约 次运算(常数更小)
两者在 的数据范围下都毫无压力,推荐使用版本二(前缀和),代码更"竞赛"且容易扩展到 更大的场景。
五、知识扩展
5.1 前缀和模板
前缀和是竞赛中最常用的技巧之一,用于快速求区间和:
// 预处理
int pre[N];
pre[0] = 0;
for (int i = 1; i <= n; i++) {
pre[i] = pre[i - 1] + a[i];
}
// 查询区间 [l, r] 的和
int sum = pre[r] - pre[l - 1];5.2 约数判断
是 的约数
即 能被 整除。本题要求的是"不是约数",所以判断条件是 sum % a[k] != 0。
六、易错点
区间长度为一:单独一个元素 ,区间和就是 本身,而 ,所以任何长度为 1 的区间一定不合法。可以思考为什么——一个数永远是自身的约数。
及时 break:一旦发现某个 能整除区间和,立刻跳出检查循环,避免无意义的后续判断。
下标从 1 开始:竞赛中习惯下标从 1 开始,方便前缀和等操作。
