1183 判断整除
1183 判断整除
【算法】 递推、同余
【C++】 二维数组、取模、bool 类型
【难度】 普及−
一、题目简述
给定 个正整数,每个数前面可以添 + 号或 - 号,求和。问:所有可能的和中,是否有至少一个能被 整除?
- ,
- 序列中每个整数范围
- 输出
YES或NO(大写)
示例:,序列
1 2 4。
8 种组合的和分别是 ,没有一个能被 2 整除,输出NO。
二、解题思路
2.1 暴力行不通
每个数有 或 两种选择,共 种组合。 接近 ,暴力枚举完全不可能。
2.2 关键观察:只关心余数
题目只问"能否被 整除",不关心和的具体值。所以只需关注和对 的余数。
对 取模后,余数只有 共 种可能。,这个状态空间非常小!
2.3 状态定义
设 dp[i][j] 表示:前 个数通过加减组合,能否得到余数为 的结果。
- 从 到
- 从 到
- 值为
true表示可以,false表示不行
初始状态:(前 0 个数,和为 0,余数是 0)
目标: 是否为 true。
2.4 状态转移
处理第 个数 时,对前一行的每个可行余数 :
| 操作 | 新余数 | 含义 |
|---|---|---|
| 加 | 当前和 | |
| 减 | (非负处理) | 当前和 |
⚠️ C++ 中负数的
%结果仍为负(如-5 % 2 = -1),需要修正:((j - x) % k + k) % k。
2.5 为什么只看余数就够了?
先想一个问题:假设 ,前几个数凑出的和是 (余数 ),和凑出的是 (余数也是 ),它们对后续有区别吗?
没有区别。 因为题目只问"最终和能否被 整除",后续操作(加减更多数)只关心余数如何变化。 加 得 (余 ), 加 得 (余 ),效果完全一样。数学上这叫同余——不同值的数,只要对 的余数相同,在本题中就"等价"。
这就是为什么 是本题的关键条件——状态空间从"无穷多种和"压缩到了" 种余数"。
2.6 转移的那两行在做什么?
来看代码中最关键的两行:
dp[i][(j + x) % k] = true; // 加当前数
dp[i][(j - x + k) % k] = true; // 减当前数假设前 个数已经凑出了余数 (dp[i-1][j] == true),即:
现在处理第 个数 :
| 操作 | 新和 | 新余数 | C++ 写法 |
|---|---|---|---|
(j + x) % k | |||
(j - x + k) % k |
由于 ,所以 。余数可以直接从 和 算出,根本不需要知道 是多少!
加号那一行:(j + x) % k 很好理解,直接加完取模。
减号那一行为什么写 (j - x + k) % k?因为 C++ 里 % 对负数会给出负结果:
(1 - 3) % 5 = -2 ← C++,不是我们想要的
数学上 -2 mod 5 = 3 ← 这才是对的加一个 再取模就能修正:
(1 - 3 + 5) % 5 = 3 ← 正确💡 记忆技巧:
(j - x + k) % k就是 C++ 中确保结果非负的标准写法。
2.7 手动模拟
以样例 ,序列 [1, 2, 4] 为例:
初始:只有余数 可达(和为 0)。
dp[0]: j=0 ✓, j=1 ✗第 1 个数 :从 出发:
- 加 1:
- 减 1:
dp[1]: j=0 ✗, j=1 ✓第 2 个数 :从 出发:
- 加 2:
- 减 2:
dp[2]: j=0 ✗, j=1 ✓第 3 个数 :从 出发:
- 加 4:
- 减 4:
dp[3]: j=0 ✗, j=1 ✓最终 ,输出 NO。✓
如果把 换成 3,最终会有一条路径的余数为 0,输出
YES。
三、参考代码
版本一:二维数组(直观)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10005;
const int MAXK = 105;
bool dp[MAXN][MAXK]; // dp[i][j]: 前 i 个数能否凑出余数 j
int a[MAXN];
int main() {
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
dp[0][0] = true; // 前 0 个数,和为 0,余数 0
for (int i = 1; i <= n; i++) {
int x = a[i] % k; // 先取模,简化计算
for (int j = 0; j < k; j++) {
if (dp[i - 1][j]) {
dp[i][(j + x) % k] = true; // 加当前数
dp[i][(j - x + k) % k] = true; // 减当前数
}
}
}
cout << (dp[n][0] ? "YES" : "NO") << endl;
return 0;
}版本二:滚动数组(空间优化)
因为 只依赖 ,可以用两行轮换:
#include <bits/stdc++.h>
using namespace std;
const int MAXK = 105;
bool dp[2][MAXK]; // 只用两行
int main() {
int n, k;
cin >> n >> k;
dp[0][0] = true; // cur=0 代表第 0 行
int cur = 0;
for (int i = 1; i <= n; i++) {
int val;
cin >> val;
int x = val % k;
cur ^= 1; // 切换到下一行(0→1, 1→0)
memset(dp[cur], 0, sizeof(dp[cur])); // 清空当前行
for (int j = 0; j < k; j++) {
if (dp[cur ^ 1][j]) { // 看上一行
dp[cur][(j + x) % k] = true;
dp[cur][(j - x + k) % k] = true;
}
}
}
cout << (dp[cur][0] ? "YES" : "NO") << endl;
return 0;
}四、复杂度分析
- 时间复杂度:。,,约 次操作,轻松通过。
- 空间复杂度:(二维数组版)或 (滚动数组版,仅 100 个 bool)。
五、思维拓展
本题的核心技巧是同余 DP——将对 的余数作为状态。这个思想在很多题目中都会出现:
| 题目类型 | 状态 |
|---|---|
| 判断整除(本题) | 前 个数的和 |
| 01 背包变体 | 体积 是否可达 |
| 子集和取模 | 选若干个数,和 能否为 0 |
六、易错点
- C++ 负数取模:
(j - x) % k可能为负,必须写(j - x % k + k) % k或(j - x + k) % k(x 已经对 k 取过模的话)。 - a[i] 先取模:,因为 可能很大,先取模避免加法溢出。
- 多组数据:本题只有一组输入,无需
while(t--)。 - 输出大写:
YES/NO,不是Yes/No。
