魔法棒

思路

拿到这道题，先理清操作到底在做什么。小坤一开始有 1 根魔法棒，每次操作可以选一根魔法棒，把它"分裂"成 根（ 是正整数）。注意：原来那根消失了，变成了 根新的，所以每次操作净增 根。

时净增 0，没意义。 时，能增加的数量依次是

那问题就变成了： 能不能表示成若干个 中元素的和？

关键推导

最小的两个增量是 3 和 8，它们互质（）。根据 Chicken McNugget 定理（也叫 Frobenius 定理），用 3 和 8 做非负整数组合，不能表示的最大整数是 。也就是说，所有 的非负整数都能用若干个 3 和若干个 8 凑出来。

那小于 14 的情况呢？手动列一下 能凑出的值：

$$

凑不出的值是 。

所以 不可达当且仅当 ，即 。

除了这 7 个数以外，其他所有正整数都输出 Yes。

样例验证

  • ：，凑不出，输出 No
  • ：，先分裂出 9 根（），再分裂一根出 4 根（），输出 Yes

代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    // 不可达的 n 只有这 7 个
    set<int> bad = {2,3,5,6,8,11,14};
    int t;
    scanf("%d",&t);
    while(t--){
        long long n;
        scanf("%lld",&n);
        puts(bad.count(n) ? "No" : "Yes");
    }
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine().trim());
        Set<Long> bad = new HashSet<>(Arrays.asList(2L,3L,5L,6L,8L,11L,14L));
        StringBuilder sb = new StringBuilder();
        while (t-- > 0) {
            long n = Long.parseLong(br.readLine().trim());
            sb.append(bad.contains(n) ? "No" : "Yes").append('\n');
        }
        System.out.print(sb);
    }
}

import sys
input = sys.stdin.readline

bad = {2, 3, 5, 6, 8, 11, 14}
t = int(input())
out = []
for _ in range(t):
    n = int(input())
    out.append("No" if n in bad else "Yes")
print('\n'.join(out))

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    const bad = new Set([2, 3, 5, 6, 8, 11, 14]);
    const t = parseInt(lines[0]);
    const out = [];
    for (let i = 1; i <= t; i++) {
        const n = parseInt(lines[i]);
        out.push(bad.has(n) ? "No" : "Yes");
    }
    console.log(out.join('\n'));
});

复杂度分析

  • 时间复杂度: ，每组测试数据 查表
  • 空间复杂度: ，只存了 7 个常量

总结

这题乍一看像搜索或 DP，但仔细一分析，每次操作的净增量集合是 。既然 3 和 8 已经互质了，后面的大数其实不影响结论——Frobenius 定理直接告诉你，大于 13 的数都能凑出来。小于等于 13 的手动列举一下就行，最终就是 7 个不可达的数，打个表完事。数论题最怕的就是想复杂了，这题的核心就是一个 Chicken McNugget 定理。