首页 > 代码库 > (简单) POJ 1426 Find The Multiple，BFS+同余。
(简单) POJ 1426 Find The Multiple，BFS+同余。
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.
大意就是说求一个只有0，1的数，是n的倍数。
其实是一个水题，第一遍做的时候直接枚举1，10，11，100，101，110，111...一直这样下去，然后就过了。。。。后来看了一下题解，说可以用BFS+同余来做，然后就试了一下，时间减去了不少。
而且这个题目对于n是偶数或者n是5的倍数可以直接求出n／2或n／5的来然后加个0就好了。。。
这是第一遍的代码：
#include<iostream>#include<cstring>using namespace std;long long ans[300];bool panduan(int a,int b){ long long num=0; long long base=1; while(b) { if(b%2) num+=base; base*=10; b/=2; } if(num%a==0) { ans[a]=num; return 1; } return 0;}int main(){ int cou=0; for(int i=1;i<=200;i+=2) if(i%5) { for(int j=1;j<(1<<18);++j) if(panduan(i,j)) { break; } } int k,rem; ios::sync_with_stdio(false); for(cin>>k;k;cin>>k) { rem=0; while(k%2==0) { k/=2; ++rem; } while(k%5==0) { k/=5; ++rem; } cout<<ans[k]; for(int i=0;i<rem;++i) cout<<0; cout<<endl; } return 0;}
这是第二遍的：
#include<iostream>#include<cstdio>#include<cstring>#include<utility>using namespace std;int que[10000000],las,fir;void showans(int x){ int ans[500]; int cou=0; while(x) { if(x&1) ans[cou++]=1; else ans[cou++]=0; x=x>>1; } for(int i=cou-1;i>=0;--i) cout<<ans[i]; cout<<endl;}inline void getans(int n){ las=fir=0; int cou=0; int temp; que[las++]=1; while(las-fir) { ++cou; temp=que[fir++]; if(!temp) { showans(cou); return; } que[las++]=(temp*10)%n; que[las++]=(temp*10+1)%n; }}int main(){ ios::sync_with_stdio(false); int n; for(cin>>n;n;cin>>n) { getans(n); } return 0;}
(简单) POJ 1426 Find The Multiple，BFS+同余。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。