Find The Multiple (poj 1426 bfs)-白红宇

Find The Multiple (poj 1426 bfs)

阅读量：6080 次

发布时间：2019-06-20

本文共 2116 字，大约阅读时间需要 7 分钟。

Language: Default

Find The Multiple

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 18454		Accepted: 7461		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

Sample Output

10100100100100100100111111111111111111

Source

题意：输入整数n，求一个只由1和0两个数字组成的十进制整数m，m是整数n（200以内）的k倍，且要求k最小。

思路：运用同余定理+bfs,。

代码：

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            #include 
            
             #include 
             
              #include 
              
               #pragma comment (linker,"/STACK:102400000,102400000")#define maxn 1005#define MAXN 2005#define INF 0x3f3f3f3f#define pi acos(-1.0)#define eps 1e-6typedef long long ll;using namespace std;struct Node{ int num; int mod; Node *pre;//记录路径};int N;int visit[maxn];void print(Node *x)//递归输出路径{ if (x->pre==NULL) printf("%d",x->num); else { print(x->pre); printf("%d",x->num); }}void bfs(){ int i; queue
               
                Q; memset(visit,0,sizeof(visit)); Node sst,*now=new Node; visit[1]=1; while (!Q.empty()) Q.pop(); sst.mod=1;sst.num=1;sst.pre=NULL; Q.push(sst); while (!Q.empty()) { Node *st=new Node; *st=Q.front(); Q.pop(); if (st->mod==0) { print(st); printf("\n"); return ; } for (i=0;i<2;i++) { int xx=(st->mod*10+i)%N; if (!visit[xx]) { now->mod=xx; now->num=i; now->pre=st; Q.push(*now); visit[xx]=1; } } } return ;}int main(){ while (scanf("%d",&N)&&N) { if (N==1) { printf("1\n"); continue; } bfs(); } return 0;}

转载于:https://www.cnblogs.com/i8888/p/4043995.html

你可能感兴趣的文章