/*
题意：找出一个0和1组成的数字能整除n
DFS：200的范围内不会爆long long，DFS水过~
*/
/************************************************
Author :Running_Time
Created Time :2015-8-2 14:21:51
File Name :POJ_1426.cpp
*************************************************/ #include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std; typedef long long ll;
const int MAXN = 1e4 + ;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + ;
ll n;
bool ok; void DFS(ll x, int step, int dep) {
if (ok) return ;
if (step >= dep) return ;
if (x % n == ) {
printf ("%I64d\n", x);
ok = true; return ;
}
DFS (x * , step + , dep);
DFS (x * + , step + , dep);
} int main(void) { //POJ 1426 Find The Multiple
while (scanf ("%I64d", &n) == ) {
if (!n) break;
ok = false; ll dep = ;
while (true) {
if (ok) break;
DFS (, , dep); dep++;
}
} return ;
}
/*
BFS+同余模定理：mod数组保存，每一位的余数，当前的数字由少一位的数字递推，
比如4(100)可以从2(10)递推出，网上的代码太吊，膜拜之
详细解释：http://blog.****.net/lyy289065406/article/details/6647917
*/
/************************************************
Author :Running_Time
Created Time :2015-8-2 15:14:33
File Name :POJ_1426_BFS.cpp
*************************************************/ #include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std; #define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int MAXN = 1e6 + ;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + ;
int mod[MAXN];
int ans[MAXN]; int main(void) {
int n;
while (scanf ("%d", &n) == ) {
if (!n) break;
mod[] = ; int i;
for (i=; mod[i-]; ++i) {
mod[i] = (mod[i/] * + (i&)) % n; //BFS双入口模拟
}
int t = ; i--;
while (i) {
ans[++t] = i & ;
i /= ;
}
while (t) {
printf ("%d", ans[t--]);
}
puts ("");
} return ;
}
BFS