Pagini recente » Cod sursa (job #3187992) | Cod sursa (job #2892627) | Cod sursa (job #3209896) | Cod sursa (job #829243) | Cod sursa (job #2509841)
#include <iostream>
#include <cstdio>
using namespace std;
const int SIZE_MAX = 2000000;
int ult[SIZE_MAX],pred[SIZE_MAX];
int q[SIZE_MAX];
int cmmdc(int a, int b){
int r;
while(a%b){
r = a%b;
a = b;
b = r;
}
return b;
}
int main()
{
FILE *fin, *fout;
int a,b,m,st,dr,nr,next;
bool solved;
fin = fopen("multiplu.in","r");
fout = fopen("multiplu.out","w");
fscanf(fin,"%d %d",&a,&b);
m = a*b/cmmdc(a,b);
st = 0, dr = -1;
for(int i=0; i<m; i++)
ult[i] = -1;
q[++dr] = 1, ult[1] = 1, pred[1] = 0;
solved = false;
while(!solved){
nr = q[st++];
if(nr == 0){
solved = true;
continue;
}
next = nr*10%m;
if(ult[next] == -1){
ult[next] = 0;
pred[next] = nr;
q[++dr] = next;
}
next = (next+1)%m;
if(ult[next] == -1){
ult[next] = 1;
pred[next] = nr;
q[++dr] = next;
}
}
dr = -1;
while(nr != 1){
q[++dr] = ult[nr];
nr = pred[nr];
}
q[++dr] = ult[nr];
while(dr >= 0){
fprintf(fout,"%d",q[dr]);
dr--;
}
fclose(fin);
fclose(fout);
return 0;
}