1950D - 二进制小数的乘积 详细题解（官方标程版）

一、题目翻译（规范格式，数字/公式全加$）

题目名称

D. 二进制小数的乘积

题目描述

如果一个正整数的十进制表示中只包含数字 $0$ 和 $1$，那么这个数被称为二进制十进制数。 例如：$1010111$ 是二进制十进制数，而 $10201$ 和 $787$ 不是。

给定一个数 $n$，你需要判断 $n$ 是否可以表示为若干个（不一定互不相同）二进制十进制数的乘积。

输入格式

• 第一行包含一个整数 $t$（$1 \le t \le 5 \cdot 10^4$），表示测试用例数量。
• 每个测试用例一行，包含一个整数 $n$（$1 \le n \le 10^5$）。

输出格式

如果 $n$ 可以表示为二进制十进制数的乘积，输出 $\texttt{YES}$；否则输出 $\texttt{NO}$。

---

二、标程核心思路

1. 预处理

首先预处理出所有不超过 $10^5$ 的二进制十进制数。 方法：遍历 $1 \sim 10^5$ 的所有数，判断每一位是否仅为 $0$ 或 $1$。

2. 合法判定规则（标程递归定义）

我们称一个数是好数（合法），当且仅当：

• $n = 1$，或者
• 存在一个二进制十进制数 $i>1$，使得 $i \mid n$，且 $\dfrac{n}{i}$ 是好数。

3. 关键性质

• 不超过 $10^5$ 的二进制十进制数不超过 $32$ 个，数量极少。
• 因此直接暴力递归/循环除法即可通过，无需记忆化。

---

三、标程解法公式

1. 二进制十进制数判定

对数字 $x$，对 $10$ 取模，每一位只能是 $0$ 或 $1$：

$$\forall d \in \text{digits}(x),\ d \in \{0,1\}$$

2. 合法性判定

$$\text{is\_good}(n) = \begin{cases} \text{true} & n=1 \\ \bigvee\limits_{\substack{i \in \text{bin-dec} \\ i>1,\ i \mid n}} \text{is\_good}\left(\dfrac{n}{i}\right) & \text{else} \end{cases} $$

3. 复杂度上界（标程数学分析）

递归复杂度上界：

$$T(n) \leq 2T\left(\left\lfloor\frac{n}{10}\right\rfloor\right) + 4T\left(\left\lfloor\frac{n}{100}\right\rfloor\right) + 26T\left(\left\lfloor\frac{n}{1000}\right\rfloor\right) $$

由 Akra-Bazzi 定理：

$$T(n) \in \mathcal{O}(n^{\log_{10}\alpha}) \approx \mathcal{O}(n^{0.635}) $$

其中 $\alpha$ 是方程

$$\alpha^3 = 2\alpha^2 + 4\alpha + 26$$

的唯一实根。

更精确估计可得：

$$T(n) \in \mathcal{O}(n^{0.587})$$

---

四、标程完整 AC 代码（可直接提交）

#include <bits/stdc++.h>
using namespace std;

vector<int> bin;

// 判断是否是二进制十进制数
bool is_bin(int x) {
    while (x) {
        int d = x % 10;
        if (d != 0 && d != 1) return false;
        x /= 10;
    }
    return true;
}

// 预处理所有 <=1e5 的二进制十进制数
void pre() {
    for (int i = 1; i <= 100000; ++i) {
        if (is_bin(i)) {
            bin.push_back(i);
        }
    }
}

// 判断 n 是否合法（标程暴力法）
bool check(int n) {
    if (n == 1) return true;
    for (int x : bin) {
        if (x > n) break;
        if (n % x == 0 && x > 1) {
            if (check(n / x)) {
                return true;
            }
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    pre();
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        cout << (check(n) ? "YES" : "NO") << '\n';
    }
    return 0;
}

五、标程总结

1. 预处理 $\le 10^5$ 的所有二进制十进制数（共约 $32$ 个）。
2. 对每个 $n$ 暴力尝试用二进制十进制数反复除。
3. 能除到 $1$ 输出 $\texttt{YES}$，否则 $\texttt{NO}$。
4. 时间复杂度极优，可轻松处理 $t=5\cdot 10^4$。

需要我把所有合法答案打表生成，做成 $\mathcal{O}(1)$ 极速版代码吗？