Find The Multiple,POJ,1426

题目描述：

给定一个正整数 ( N )，你的任务是找到一个最小的正整数 ( X )，使得 ( N \times X ) 的十进制表示中只包含数字 0 和 1。

输入：

输入包含多个测试案例。每个测试案例占一行，包含一个正整数 ( N )（( 1 \leq N \leq 1000 )）。输入以一个负数结束。

输出：

对于每个测试案例，输出一行，包含一个最小的正整数 ( X )，使得 ( N \times X ) 的十进制表示中只包含数字 0 和 1。

示例输入：

2 6 19 -1

示例输出：

5 2 111

解题思路：

这个问题可以通过广度优先搜索（BFS）来解决。基本思路是将问题转化为寻找一个最小的 ( X )，使得 ( N \times X ) 的十进制表示中只包含数字 0 和 1。我们可以从 ( X = 1 ) 开始，逐步增加 ( X )，检查 ( N \times X ) 是否满足条件。

具体步骤如下：

1. 初始化：使用一个队列来进行广度优先搜索，初始时将 ( X = 1 ) 入队。
2. BFS遍历：每次从队列中取出一个 ( X )，计算 ( N \times X )，检查其十进制表示是否只包含数字 0 和 1。
   • 如果满足条件，则输出 ( X ) 并结束当前测试案例。
   • 如果不满足条件，将 ( X ) 的两个“子节点” ( 10X ) 和 ( 10X + 1 ) 入队，继续搜索。
3. 终止条件：当输入为负数时，结束程序。

代码实现：

#include #include #include

int main() { int n; while (cin >> n && n > 0) { queue q; q.push(1); while (!q.empty()) { int x = q.front(); q.pop(); if (check(n, x)) { cout << x << endl; break; } q.push(x 10); q.push(x 10 + 1); } } return 0; }

解释：

1. check函数：用于检查 ( N \times X ) 的十进制表示是否只包含数字 0 和 1。
2. 主函数：
   • 读取输入 ( N )，当 ( N ) 为负数时结束。
   • 使用队列进行广度优先搜索，初始时将 ( X = 1 ) 入队。
   • 每次从队列中取出一个 ( X )，检查 ( N \times X ) 是否满足条件。
   • 如果满足条件，输出 ( X ) 并结束当前测试案例。
   • 否则，将 ( X ) 的两个“子节点” ( 10X ) 和 ( 10X + 1 ) 入队，继续搜索。

这种方法虽然简单，但可能会遇到较大的数字，导致计算和存储开销较大。实际应用中可以通过优化存储和计算方式来提高效率。