首页 > 代码库 > 1109 01组成的N的倍数
1109 01组成的N的倍数
1109 01组成的N的倍数
基准时间限制：1 秒 空间限制：131072 KB
给定一个自然数N，找出一个M，使得M > 0且M是N的倍数，并且M的10进制表示只包含0或1。求最小的M。
例如：N = 4，M = 100。
Input
输入1个数N。(1 <= N <= 10^6)
Output
输出符合条件的最小的M。
Input示例
4
Output示例
100
和http://www.cnblogs.com/zzuli2sjy/p/5731745.html一样；
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cstring> 4 #include <cmath> 5 #include <iostream> 6 #include <algorithm> 7 #include <map> 8 #include <queue> 9 #include <vector> 10 #include<set> 11 using namespace std; 12 typedef long long LL; 13 bool flag[6000000]; 14 int ans[20]; 15 set<int>que; 16 set<int>::iterator it; 17 typedef struct pp 18 { 19 int mod; 20 int id; 21 int pre; 22 int digit; 23 pp() 24 { 25 pre=-1; 26 } 27 } ss; 28 ss bns[1000000]; 29 int ask[1000000]; 30 int cp[2000000]; 31 int bfs(int n,int m); 32 int main(void) 33 { 34 int i,j,k; 35 while(scanf("%d",&k)!=EOF) 36 { 37 int n; 38 int m; 39 que.clear(); 40 cp[0] = 0;cp [1] = 1; 41 n = 2; 42 ans[0]=cp[0]; 43 int uu=cp[0]; 44 int t=1; 45 for(i=1;i<n;i++) 46 { 47 if(cp[i]!=uu) 48 { 49 ans[t++]=cp[i]; 50 uu=cp[i]; 51 } 52 } 53 54 if(k==0)printf("0\n"); 55 else 56 { 57 int sum=0; 58 int id=bfs(t,k); 59 if(id==-1) 60 { 61 printf("0\n"); 62 } 63 else 64 { 65 while(id!=-1) 66 { 67 ask[sum++]=bns[id].digit; 68 id=bns[id].pre; 69 } 70 for(i=sum-1; i>=0; i--) 71 { 72 printf("%d",ask[i]); 73 } 74 printf("\n"); 75 } 76 } 77 } 78 return 0; 79 } 80 int bfs(int n,int m) 81 { 82 int i,j,k; 83 int kk=0; 84 memset(flag,0,sizeof(flag)); 85 queue<ss>stc; 86 for(i=0; i<n; i++) 87 { 88 int mod=ans[i]%m; 89 if(!flag[mod]&&ans[i]!=0) 90 { 91 flag[mod]=true; 92 bns[kk].id=kk; 93 bns[kk].mod=mod; 94 bns[kk].pre=-1; 95 bns[kk].digit=ans[i]; 96 stc.push(bns[kk]); 97 kk++; 98 } 99 }100 while(!stc.empty())101 {102 ss tt=stc.front();103 stc.pop();104 for(i=0; i<n; i++)105 {106 int mod=(tt.mod*10+ans[i])%m;107 if(!flag[mod])108 {109 bns[kk].id=kk;110 bns[kk].pre=tt.id;111 bns[kk].mod=mod;112 bns[kk].digit=ans[i];113 if(mod==0)114 {115 return kk;116 }117 stc.push(bns[kk]);118 kk++;119 flag[mod]=true;120 }121 }122 }123 return -1;124 }
1109 01组成的N的倍数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。