POJ 1426 Find The Multiple：DFS 構造僅含 0/1 的 n 的倍數

問題描述

給定 n ≤ 200，找出非零倍數 m，使其十進制只含數字 0 和 1。保證存在 ≤ 100 位數的解。

DFS + 剪枝

從最高位遞歸構造：每位只能加 0 或 1。當前數 x，若 x % n == 0 輸出。限制最多 19 位（題目保證 100 位內有解，19 位足夠覆蓋 2^19 > 200 的鴿巢原理）。

代碼

#include <cstdio>
using namespace std;

int n, found;
void dfs(unsigned long long x, int len) {
    if (found) return;
    if (x % n == 0) { printf("%llu\n", x); found = 1; return; }
    if (len == 19) return; // 最大 19 位
    dfs(x * 10, len + 1);
    dfs(x * 10 + 1, len + 1);
}

int main() {
    while (scanf("%d", &n), n) {
        found = 0;
        dfs(1, 0);
    }
    return 0;
}

關鍵點

• 用 unsigned long long 防溢出（19 位 < 2^64）
• 先嘗試加 0 再加 1，得到字典序最小解（任意解均可）
• 長度限制 19 由鴿巢原理保證：2^19 = 524288 > 200，前綴和模 200 必有重複，構造出解

樣例

輸入: 2 6 19 0
輸出: 10 100100100100100100 111111111111111111