Find The Multiple
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
6
2
19
0
Sample Output
10
100100100100100100
111111111111111111
Source
题目类型：BFS
算法分析：从最高位”1”开始搜索，每次向低位扩展(0或者1)，然后判断最后的结果是否能够整除n
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
#pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7FFFFFFF; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 2e6 + 6666; int n; LL bfs () { queue <LL> qu; qu.push (1LL); while (!qu.empty ()) { LL tt = qu.front (); qu.pop (); if (tt * 10 % n == 0) return tt * 10; if ((tt * 10 + 1) % n == 0) return tt * 10 + 1; qu.push ((tt * 10)); qu.push ((tt * 10 + 1)); } return -1; } int main() { // CFF; while (scanf ("%d", &n) != EOF) { if (n == 0) break; printf ("%lld\n", bfs ()); } return 0; } |
题目类型：BFS+同余
算法分析：对于上面的算法进行优化(每次计算利用前面计算好的余数)，最后得到进行*10操作的数量，反推回去就是结果
代码：http://blog.csdn.net/lyy289065406/article/details/6647917
- « 上一篇：poj1376
- poj3087：下一篇 »