Pagini recente » Statistici Husaru-Nechita George (husarugeorge) | Cod sursa (job #1959568) | Cod sursa (job #1962220) | Monitorul de evaluare | Cod sursa (job #1736649)
#include<cstdio>
#include<queue>
#include<bitset>
#define MAXD 2000010
using namespace std;
char s[MAXD];
int previous[MAXD];
bitset<MAXD> digit,seen;
queue<int> Queue;
int Gcd(int a,int b){
int r;
while(b!=0){
r=a%b;
a=b;
b=r;
}
return a;
}
int main(){
freopen("multiplu.in","r",stdin);
freopen("multiplu.out","w",stdout);
int a,b,n,remainder,newRemainder,i,digits=0;
scanf("%d%d",&a,&b);
n=(a*b)/Gcd(a,b);
seen[1]=1;
Queue.push(1);
digit[1]=1;
previous[1]=-1;
while(seen[0]==0){
remainder=Queue.front();
Queue.pop();
for(i=0;i<=1;i++){
newRemainder=(remainder*10+i)%n;
if(seen[newRemainder]==0){
seen[newRemainder]=1;
digit[newRemainder]=i;
previous[newRemainder]=remainder;
Queue.push(newRemainder);
}
}
}
i=0;
while(i!=-1){
digits++;
s[digits]=digit[i]+'0';
i=previous[i];
}
for(i=digits;i>=1;i--)
printf("%c",s[i]);
return 0;
}