判断整除

题目描述

给定 $N$ 个正整数 $a_i$ （ $2 < N < 10000$ ， $2 < k < 100$ ， $0 \leqslant a_i \leqslant 10000$ ），在每个数前放 + 或 - 后求和；只要 $2^N$ 种符号方案中存在一种和为 $k$ 的倍数（ $0$ 、 $-3$ 、 $-6$ 都算 $3$ 的倍数）就称该序列可被 $k$ 整除。输入第一行为 $N$ 与 $k$ ，第二行为 $N$ 个整数；输出 YES 或 NO。样例输入 3 2 / 1 2 4，样例输出 NO（ $1$ 是唯一的奇数项，无论符号怎么取和都是奇数）。

思路

$2^N$ 种符号方案无法枚举，但前缀和只有 $k$ 种余数，余数相同的方案完全等价、可以合并。用 reach[r] 记录处理完前 $i$ 个数后哪些余数可达，初值只有 reach[0] = 1；每加入 $a_i$ 就由 $D_{i-1}$ 在模 $k$ 下平移出 $D_{i-1}+a_i$ 与 $D_{i-1}-a_i$ 两支，最后查 reach[0] 即可。因为只看余数，可以先把每个 $a_i$ 归约到 $a_i \bmod k$ ，总复杂度 $O(Nk)$ 。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-29 23:03
# update_at: 2026-09-29 23:08

import sys


def shift_ring(mask: int, step: int, k: int, full: int) -> int:
    """把「可达余数集合」整体沿环平移 step 步，超出的位绕回低位（循环移位）。

    mask 的第 r 位为 1 表示余数 r 可达；每位移到 r+step，所以 +a 是环形左移 a 位，-a 是环形左移 k-a 位。
    """
    step %= k                            # 归约到 [0,k)：既完成 a 取模，也把 -a 折成 k-(a mod k)
    return (mask << step | mask >> (k - step)) & full


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    next(data)                           # n：循环直接迭代剩余整数，这里只跳过它
    k = next(data)
    full = (1 << k) - 1                  # k 个余数位全为 1 的封顶掩码
    reach = 1                            # 只有余数 0 可达（空序列和为 0）

    for a in data:                       # 逐个数字决定前面放 + 还是 -
        reach = shift_ring(reach, a, k, full) | shift_ring(reach, -a, k, full)

    print("YES" if reach & 1 else "NO")  # 第 0 位仍是 1 就说明存在和为 k 倍数的符号方案


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 05:11
 * update_at: 2026-10-05 05:11
 */
// main.cpp：判断整除。2^n 种符号方案只有 k 个余数状态，保留「可达余数集合」逐个数字推进。
#include <iostream>
using namespace std;

typedef long long ll;

const int MAXN = 10005;
const int MAXK = 105;

ll n, k;
ll a[MAXN];        // a[i] 已归约到 [0, k)，加号减号只关心余数
char reach[MAXK];  // reach[r] = 1 表示处理完当前前缀后余数 r 可达
char nxt[MAXK];    // 加入 a[i] 之后的可达余数集合

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] %= k; // 只看余数：s * a 与 s * (a mod k) 模 k 同余
    }

    reach[0] = 1; // 空序列的和为 0

    for (ll i = 1; i <= n; i++) {
        for (ll r = 0; r < k; r++) nxt[r] = 0;
        for (ll r = 0; r < k; r++) {
            if (!reach[r]) continue;
            nxt[(r + a[i]) % k] = 1;          // 第 i 个数前放 +
            nxt[(r - a[i] + k) % k] = 1;      // 第 i 个数前放 -
        }
        for (ll r = 0; r < k; r++) reach[r] = nxt[r];
    }

    if (reach[0])
        cout << "YES" << "\n";
    else
        cout << "NO" << "\n";

    return 0;
}

目录

题目描述

思路

参考代码