解题思路

这个问题要求我们找到一个由数字$0$和$1$组成的非零整数$m$，使得$m$是给定整数$n$的倍数。由于$n$的范围较小（$1 \leq n \leq 200$），我们可以采用深度优先搜索（DFS）的方法来逐步构造可能的数字，并检查它们是否是$n$的倍数。

关键步骤：

1. 深度优先搜索（DFS）：从数字$1$开始，逐步在末尾添加$0$或$1$，生成新的数字。
2. 剪枝优化：为了避免无限递归和减少计算量，设置一个最大位数限制（例如$18$位），当数字长度超过这个限制时停止搜索。
3. 模运算检查：在生成每个数字时，通过模运算检查它是否是$n$的倍数。如果是，则立即返回该数字。

具体实现：

1. 初始化：从数字$1$开始搜索。
2. 递归生成数字：
   • 在每一步，当前数字可以扩展为两个新数字：在末尾添加$0$或$1$。
   • 每次扩展后，检查新数字是否是$n$的倍数。
3. 终止条件：
   • 找到一个满足条件的数字（即$m \% n == 0$且$m \neq 0$）。
   • 数字长度超过预设的最大位数（例如$18$位）。

代码解释：

• dfs函数：递归生成数字，参数$r$表示当前数字，$pos$表示当前数字的位数。
  • 如果$pos$超过$18$位或已经找到答案（$ans$不为$0$），则直接返回。
  • 检查当前数字$r$是否是$n$的倍数，如果是，则赋值给$ans$并返回。
  • 递归调用$dfs$，分别在当前数字末尾添加$0$和$1$。
• 主函数：读取输入$n$，调用$dfs$函数搜索答案，并输出结果。

代码实现

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
typedef long long ll;
ll n, ans;

void dfs(ll r, ll pos) {
    if (pos > 18 || ans) return; // 剪枝：位数超过18或已找到答案
    if (r % n == 0 && r) { // 找到满足条件的数字
        ans = r;
        return;
    }
    dfs(r * 10, pos + 1); // 末尾添加0
    dfs(r * 10 + 1, pos + 1); // 末尾添加1
}

int main() {
    while (scanf("%lld", &n) && n) {
        ans = 0;
        dfs(1, 0); // 从数字1开始搜索
        printf("%lld\n", ans);
    }
    return 0;
}