Astria's Blog

主题

4219-找倍数-2 ​

原题链接

给定一个正整数 ( n )，请你找到一个它的非零倍数 ( m )。

要求 ( m ) 中只包含数字 0 或 1，并且总位数不超过 100 位。

输入格式
输入包含多组测试数据。
每组数据占一行，包含一个正整数 ( n )。
当输入 ( n=0 ) 时，表示输入结束。

输出格式
每组数据输出一行 ( m )。
如果方案不唯一，则输出任意合理方案均可。

数据范围
( 1 \leq n \leq 200 )

输入样例：

2
6
19
0

输出样例：

10
100100100100100100
111111111111111111

分析

  • 难点在于取模。注意：11 % 2 = ((1 × 10) % 2 + 1) % 2

代码

cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;

queue<pair<string, ll>> q; // 用于BFS搜索

int main() {
    while (cin >> n && n) {
        while (!q.empty()) q.pop(); // 清空队列
        q.push({"1", 1}); // 从"1"开始搜索，取模余数为1
        
        while (!q.empty()) {
            auto p = q.front();
            q.pop();
            if (p.second == 0) { // 余数为0，说明找到了答案
                cout << p.first << endl;
                break;
            }
            // 分别尝试在末尾补0和补1，并更新取模结果
            q.push({p.first + "0", (p.second * 10) % n});
            q.push({p.first + "1", (p.second * 10 + 1) % n});
        }
    }
    return 0;
}