题目链接：POJ 1426
题意：
给一个正数n找出一个n的倍数，并且这个倍数各个位上的数字不是0就是1。
如果有多种答案，输出一个即可。
分析：
首先想到了大数乘法，由于要保证每个位上的数字非0即1，那么由n的最后一位不为0的数就可以限制乘数。例如n最后一位不为0的数如果是1，那么乘数的最后一位只能是1（如果是其他数字那么相乘得到的数最后一位一定不满足非0即1）【0除外，相当于*10了，没意义】
于是写出了如下代码：
#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 105;
char p[105], ans[105], tmp[maxn];
int carry, k, t, r;int valid(char s[])
{
for (int i = 0;s[i];i++)
if (!(s[i] == '0' || s[i] == '1')) return 0;
return 1;
}void reverse(char s[])
{
int lens = strlen(s);
for (int i = 0;i < lens / 2;i++)
{
char c1 = s[i];
s[i] = s[lens - 1 - i];
s[lens - 1 - i] = c1;
}
}void mul(char a[], char b[], char d[])
{
reverse(a);
reverse(b);
int lena = strlen(a);
int lenb = strlen(b);
int i, j;
j = carry = 0;
for (int p = 0;p < lena + lenb - 1;p++)
d[p] = '0';
while (b[j])
{
for (i = 0;i <lena;i++)
{
int t = (a[i] - '0') * (b[j] - '0') + carry + d[i + j] - '0';
carry = t / 10;
t %= 10;
d[i + j] = t + '0';
}
j++;
}
k = lena + lenb - 1;
d[k++] = carry + '0';
d[k] = '\0';
reverse(d);
while (d[0] == '0'&&strlen(d)>1)//清楚前缀0
{
int i;
for (i = 0;i < (strlen(d) - 1);i++)
d[i] = d[i + 1];
d[i] = '\0';
}
}int main()
{
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
while (~scanf("%s",p))
{
if (strcmp(p, "0") == 0) break;
if (valid(p))
{
puts(p);
continue;
}
int len = strlen(p);
for (int i = len - 1;;i--)
{
if (p[i] != '0')
{
t = p[i] - '0';
break;
}
}
if (t == 1) r = 11;
else if (t == 2) r = 5;
else if (t == 3) r = 7;
else if (t == 4) r = 5;
else if (t == 5) r = 2;
else if (t == 6) r = 5;
else if (t == 7) r = 3;
else if (t == 8) r = 5;
else if (t == 9) r = 9;
for (int i = r;;i += 10)
{
sprintf(tmp, "%d", i);
mul(tmp, p, ans);
if (valid(ans)) break;
}
puts(ans);
}
return 0;
}但是TLE了！到网上找到了一种解题报告的思路：
用BFS搜索，首先从1开始，那么下一个入队列的是1*10和1*10+1，依此类推，代码很简洁。
#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
long long ans,cur;
int n;
long long bfs(int n)
{queue<long long> q;q.push(1);while(1){cur=q.front();q.pop();if (cur%n == 0) return cur;q.push(cur * 10);q.push(cur * 10+1);}
}
int main()
{
#ifdef LOCALfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifwhile (cin>>n){if (n == 0) break;ans = bfs(n);cout << ans << endl;}return 0;
}又看到一种用DFS的方法，想法一样。
需要注意的是：
①一层递归相当于位数加一，而long long型最多存储19位，多了就不行了，所以递归时要传递一个参数，当==20时，回溯。
②设置一个bool类型，用以标记是否找到正确的倍数。
代码如下：
#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;long long ans, cur;
int n;
bool flag;
void dfs(int k,long long t)
{if (flag) return;if (k == 20) return;if (t%n == 0){flag = true;cout << t << endl;return;}dfs(k + 1, t * 10);dfs(k + 1, t * 10 + 1);
}
int main()
{
#ifdef LOCALfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifwhile (cin >> n){if (n == 0) break;flag = false;dfs(1, 1);}return 0;
}100100100100100100 111111111111111111DFS做出来的也是这个结果，而BFS做出来的是
1110
11001
！！！！！
o(╯□╰)o