Cod sursa(job #391518)
#include <stdio.h>
#define NMAX 2000010
int D[NMAX];
int v[NMAX], sol[NMAX], pre[NMAX];
bool anter[NMAX];
int m;
int cmmdc(int a,int b){
if(a % b == 0)
return b;
return cmmdc(b, a%b);
}
void adauga(int x,int c){
int p = ((long long) x*10 + c)%m;
if(D[p]) return;
D[p] = D[x] + 1;
v[++v[0]] = p;
pre[p] = x;
anter[p] = c;
}
int main(){
freopen("multiplu.in", "r", stdin);
freopen("multiplu.out", "w", stdout);
int a, b;
scanf("%d%d", &a, &b);
m = a/cmmdc(a,b) * b;
v[++v[0]] = 1;
for(int i = 1; v[v[0]]; ++i){
adauga(v[i], 0);
if(!v[v[0]]) break;
adauga(v[i], 1);
}
int x = 0;
while(pre[x]){
sol[++sol[0]] = anter[x];
x = pre[x];
}
sol[++sol[0]] = 1;
for(int i = sol[0]; i ; --i)
printf("%d", sol[i]);
printf("\n");
}