Find The Multiple
| Time Limit: 1000MS | Memory Limit: 10000K | |||
| Total Submissions: 18012 | Accepted: 7297 | Special Judge | ||
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
Source
開始做这道题的时候半天没有读懂题意，例子数据是吓人的，把一个单词理解错误，multiple在这里是倍数的意思。这个题目就是要求我们求出给定的一个数的一个由0,1组成的倍数，100位也是吓人的。開始看那个例子，全然不好理解啊。看了半天没有理解题意，也想不到要用bfs来做。看了别人的一点提示就清晰啦。就用一个队列来模拟运算的过程，假设能够整除就直接输出，不能整除把他*10，和*10+1入队；
由于都是0,1组成的倍数，所以组成直接*10。或者是*10+1；
以下是用stl写的，第一次用stl写。有点水，用stl在poj上c++过不了，g++才过的；
#include <iostream>
#include <queue>
#include <cstdio>
using namespace std;
void bfs(int n)
{
queue<__int64>q;//这里后面的数据可能会有大的，所以用个64位的就够了
q.push(1);
while(!q.empty())
{
__int64 x;
x=q.front();
q.pop();
if(x%n==0)//能够整除就直接输出
{
printf("%I64d
",x);
return ;
}
q.push(x*10);//把x的10的倍数入队。
q.push(x*10+1);
}
}
int main()
{
int n;
while(scanf("%d",&n)&&n)
{
bfs(n);
}
return 0;
}自己用数组模拟队列写了一下；貌似效率比stl好了一些；
主要的思想都是一样的；
#include <cstdio>
#include <cstring>
long long q[2000000];
void bfs(int n)
{
int front=0;
int rear=0;
q[front]=1;
rear++;
long long temp;
while(rear>front)
{
temp=q[front];
if(temp%n==0)
{
break;
}
temp*=10;
q[rear]=temp;
rear++;
q[rear]=temp+1;
rear++;
front++;
}
printf("%lld
",temp);
}
int main()
{
int n;
while(scanf("%d",&n)&&n)
{
bfs(n);
}
return 0;
}
在网上还看到了大神的代码用了同余取模定理，还是有点没看懂。还有的直接用满二叉树模拟的队列。
（a*b）%n = （a%n *b%n）%n
（a+b）%n = （a%n +b%n）%n
看到其它大神对这道的思路：
再贴一段pl大牛关于此题的分析思路。以学习：
要m整除n，那么能够用对n的余数来表示当前的状态。
搜到一个余数为0的状态就能够了。
直接bfs出去。
假设当前的余数是r。添在当前答案后面的数为,k
那么新的余数。也就是新的状态为：
( r * 10 + k ) % n 。
这样最多200个状态，判重一下。能够非常快出解。
大牛的代码：
#include<iostream>
using namespace std;
int a[524300],i,n;
int main(){
while(cin>>n){
if (!n) break;
i=1; a[1]=1%n;
while(a[i]){i++; a[i]=(a[i/2]*10+i%2)%n;}
n=0; while(i){a[n++]=i%2;i>>=1;}
while(n--) cout<<a[n]; cout<<endl;
}
return 0;
}这原来也是bfs，直接用一个满二叉树实现（左儿子是0，右儿子是1）；
还是要多学习大神们的代码~