题解 ZJUT 3121/2 二进制小数的乘积（简单版、困难版）

2025-11-18 · 题解
#ZJUT #贪心

简单版：ZJUT 3121
困难版：ZJUT 3122

题目大意

有 $t$ 次询问，每次询问给定一个整数 $n$ ，若 $n$ 可以分解为若干个所有数位都是 $0$ 或 $1$ 的正整数的乘积，则输出 YES，否则输出 NO。

解题思路

根据题面描述，「二进制小数」定义为所有数位都是 $0$ 或 $1$ 的正整数，类比枚举二进制整数的方法，可以手动枚举出所有 $10^5$ 以内的二进制小数 $1, 10, 11, 100, 101, \ldots$ ，也可以编写代码，使用 BFS 枚举二进制小数序列。BFS 枚举的具体做法为：队列初始为 $1$ ，此后不断将队首元素 $x$ 出栈，若 $x$ 不超过 $\max{n}$ 就将 $x$ 存入 vector 并将 $10x, 10x + 1$ 入栈，直到队列为空。易知 vector 中的元素是按升序存入的。

枚举出所有不大于 $n$ 的二进制小数后，思考该以何种顺序试除每个二进制小数，此时考虑贪心算法，按照从大到小的顺序用每个二进制小数试除 $n$ ，直至 $n$ 变成 $1$ 或者所有二进制小数因子都被除尽。如果 $n$ 最终为 $1$ （包括 $n$ 本身为 $1$ 或者 $n$ 除尽所有二进制小数因子后变成 $1$ 两种情况），则输出 YES，否则输出 NO。需要注意的是，虽然 $1$ 也是一个二进制小数，但不能用它作为因子试除，因为 $1 \bmod 1 = 1$ ，会造成死循环而 TLE，因此只能除到 $10$ （即 $\mathrm{nums _ 1}$ ）为止。

此外还能做一个剪枝：注意到二进制小数的个位均为 $0$ 或 $1$ ，那么倘若正整数 $n$ 可以分解为若干个二进制小数的乘积，那么 $n$ 的个位必定是 $0$ 或 $1$ 。对于个位不是 $0$ 或 $1$ 的 $n$ ，它一定无法分解为若干个二进制小数的乘积，可以直接输出 NO。

贪心正确性证明（数学归纳法）

设 $P(n)$ 表示正整数 $n$ 能分解为若干个二进制小数的乘积。

如果 $n = 1$ ， $1$ 是二进制小数，显然 $P(n)$ 为真；

如果 $n \ge 2$ ，

如果 $n$ 本身为二进制小数，显然 $P(n)$ 为真；

如果 $n$ 不是二进制小数但可以分解为若干个二进制小数的乘积，设 $n = a _ 1 ^ {k _ 1} a _ 2 ^ {k _ 2} \ldots a _ m ^ {k _ m}$ （ $a _ i$ 是二进制小数， $k _ i \in \mathbb{N _ +}$ ， $a _ 1 > a _ 2 > \ldots > a _ m$ ， $i = 1, 2, \ldots, m$ ），则根据贪心过程可得

$\begin{aligned} P(n) &= P(a _ 1 ^ {k _ 1} a _ 2 ^ {k _ 2} \ldots a _ m ^ {k _ m}) \\ &= P(a _ 2 ^ {k _ 2} a _ 3 ^ {k _ 3} \ldots a _ m ^ {k _ m}) \\ &= \cdots \\ &= P(a _ m ^ {k _ m}) \\ &= P(1) \end{aligned}$

因此 $P(n)$ 为真；

如果 $n$ 不是二进制小数也不可以分解为若干个二进制小数的乘积，设 $n = a _ 1 ^ {k _ 1} a _ 2 ^ {k _ 2} \ldots a _ m ^ {k _ m} b$ （ $a _ i$ 是二进制小数， $b$ 不是二进制小数， $k _ i \in \mathbb{N _ +}$ ， $a _ 1 > a _ 2 > \ldots > a _ m$ ， $i = 1, 2, \ldots, m$ ），则根据贪心过程可得

$\begin{aligned} P(n) &= P(a _ 1 ^ {k _ 1} a _ 2 ^ {k _ 2} \ldots a _ m ^ {k _ m} b) \\ &= P(a _ 2 ^ {k _ 2} a _ 3 ^ {k _ 3} \ldots a _ m ^ {k _ m} b) \\ &= \cdots \\ &= P(a _ m ^ {k _ m} b) \\ &= P(b) \end{aligned}$

因为 $b$ 不是二进制小数，所以 $P(n) = P(b)$ 为假。

综上所述，本题使用的贪心算法正确。

关于不能采用从小到大的顺序试除二进制小数因子的错误贪心策略，是因为从小因子开始试除，可能会将某些大因子破坏，可能使这些因子由二进制小数被破坏为非二进制小数。例如，当 $n = 1001$ 时， $1001$ 本身就是一个二进制小数，应当输出 YES，但如果从小因子开始除， $10$ 不是 $1001$ 的因子，但 $11$ 是 $1001$ 的因子， $1001 \div 11 = 91$ ,而 $91$ 无法分解为若干个二进制小数的乘积，最终将输出 NO，此时在错误的贪心策略下， $n$ 原有的二进制小数大因子 $1001$ 在除以 $11$ 被破坏为非二进制小数因子。故采用从小到大的顺序试除二进制小数因子的贪心策略错误。

复杂度分析

时间复杂度

由于最多生成 $32$ 个二进制小数，生成二进制小数序列的时间复杂度是可以忽略的常数。有 $t$ 轮询问，在每轮询问中，共有 $31$ 个二进制小数因子可能被试除， $n$ 除以每个因子的次数不超过 $5$ 次，故每轮询问的时间复杂度为 $\mathcal{O}(1)$ ， $t$ 轮询问的时间复杂度为 $\mathcal{O}(t)$ 。总时间复杂度为 $\mathcal{O}(t)$ 。

空间复杂度

vector 中最多只存储了 $32$ 个二进制小数，总空间复杂度为 $\mathcal{O}(1)$ 。

代码

#include <cstdio>
#include <queue>
#include <vector>

int t, n;
std::vector<int> nums;
const int MAX_N = 100000; // 简单版改为 MAX_N = 1000

void build_nums() {
    std::queue<int> q;
    q.push(1);

    while (!q.empty()) {
        int x = q.front();
        q.pop();
        if (x > MAX_N) continue;

        nums.push_back(x);

        q.push(x * 10);
        q.push(x * 10 + 1);
    }
}

void work(int n) {
    if (n % 10 != 0 && n % 10 != 1) {
        printf("NO\n");
        return;
    }

    for (int i = nums.size() - 1; i >= 1; i--) {
        if (n == 1) break;
      
        while (n % nums[i] == 0)
            n /= nums[i];
    }

    printf("%s\n", n == 1 ? "YES" : "NO");
}

int main() {
    scanf("%d", &t);
    build_nums();
    while (t--) {
        scanf("%d", &n);
        work(n);
    }
    return 0;
}