Find The Multiple
Time Limit: 1000MS Memory Limit: 10000K
Description
Given a positive integer n, write a program to find out a nonzero multiple m of n whose decimal representation contains only the digits 0 and 1. You may assume that n is not greater than 200 and there is a corresponding m containing no more than 100 decimal digits.
Input
The input file may contain multiple test cases. Each line contains a value of n (1 <= n <= 200). A line containing a zero terminates the input.
Output
For each value of n in the input print a line containing the corresponding value of m. The decimal representation of m must not contain more than 100 digits. If there are multiple solutions for a given value of n, any one of them is acceptable.
Sample Input
2
6
19
0
Sample Output
10
100100100100100100
111111111111111111
题目大意
多组数据，每组数据给一个整数 n ，求出一个只包含0和1的且是 n 的倍数的数字。
解题思路
思路一
很明显的搜索题，对于这个问题，暂时不知道是否会有爆 long long 的风险。所以一开始我选择了用string来存这个倍数的最终结果，每次只需要判断当前的数字 mod n是否为0即可，如果余数不为0，则继续对这个余数进行加一位0或1进行搜索；如果余数为0，即找到了这个倍数。由于这个倍数的长度是未知的，所以应当采用迭代加深，即IDDFS或者BFS来解决这个问题。BFS较为熟悉且也很容易写，故我一开始写下了如下代码：
/* 一切都是命运石之门的选择 El Psy Kongroo */
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<cmath>
#include<functional>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<double, double> pdd;
typedef pair<string, pii> psi;
typedef __int128 int128;
#define x first
#define y second
const int inf = 0x3f3f3f3f, mod = 1e9 + 7;
ll n;
string bfs(){
queue<psi> q;
q.push(make_pair("1", 1));
while(!q.empty()){
string cur = q.front().first;
ll r = q.front().second;
q.pop();
if(r == 0) return cur; //当余数为0 找到倍数
//两种状态入队
q.push(make_pair(cur + "0", (r * 10) % n));
q.push(make_pair(cur + "1", (r * 10 + 1) % n));
}
return "";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
while(cin >> n && n){
string res = bfs();
cout << res << endl;
}
return 0;
}
思路二
但是事实上，思路一的代码在POJ上，我记得是过不了的，会MLE，不过在其他平台上也许可以AC。
所以需要找到一种方式来优化存储。实际上，n的范围还是比较小的，经过打表实验，结果发现其并不会爆 long long。
随便写了个打表的程序，大概都不会爆 long long 的（写得有点烂）：
bool has_other(ll x){
string s = to_string(x);
for(auto &ch : s)
if(ch != '0' && ch != '1')
return true;
return false;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
for(int i = 1; i <= 200; i ++ ){
for(ll j = 1; j <= 100000000000; j ++ ){
ll res = i * j;
if(!has_other(res)){
cout << i << ' ' << res << endl;
break;
}
}
}
return 0;
}
由此可知，我们可以不用string来存储最终结果，直接开long long放入队列，找到最小倍数即可。
/* 一切都是命运石之门的选择 El Psy Kongroo */
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<cmath>
#include<functional>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<double, double> pdd;
typedef pair<string, pii> psi;
typedef __int128 int128;
#define x first
#define y second
const int inf = 0x3f3f3f3f, mod = 1e9 + 7;
ll n;
ll bfs(){
queue<ll> q;
q.push(1);
while(!q.empty()){
ll r = q.front();
q.pop();
if(r % n == 0) return r;
q.push(r * 10);
q.push(r * 10 + 1);
}
return -1;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
while(cin >> n && n){
ll res = bfs();
cout << res << endl;
}
return 0;
}