Pagini recente » Monitorul de evaluare | Rezultatele filtrării | Diferente pentru problema/mugur intre reviziile 5 si 9 | Borderou de evaluare (job #2731405) | Cod sursa (job #1332922)
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
struct INFO {
bool c;
int r,t;
};
INFO q[2000005];
bool r[2000005];
vector <int> sol;
inline int gcd(int a,int b) {
int r;
while(b!=0) {
r=a%b;
a=b;
b=r;
}
return a;
}
inline int lcm(int a,int b) {
int rez=gcd(a,b);
return rez*(a/rez)*(b/rez);
}
int main() {
int a,b,last,m,i,rest;
INFO temp;
freopen("multiplu.in","r",stdin);
freopen("multiplu.out","w",stdout);
scanf("%d %d",&a,&b);
temp.c=1;
temp.r=1;
temp.t=0;
q[1]=temp;
m=lcm(a,b);
i=1;
last=1;
while(1) {
///Adaug 0
rest=(q[i].r*10+0)%m;
if(!r[rest]) {
r[rest]=1;
temp.c=0;
temp.r=rest;
temp.t=i;
q[++last]=temp;
}
if(r[0])
break;
///Adaug 1
rest=(q[i].r*10+1)%m;
if(!r[rest]) {
r[rest]=1;
temp.c=1;
temp.r=rest;
temp.t=i;
q[++last]=temp;
}
if(r[0])
break;
i++;
}
for(i=last; i>=1;) {
sol.push_back(q[i].c);
i=q[i].t;
}
reverse(sol.begin(),sol.end());
for(i=0; i<sol.size(); i++)
printf("%d",sol[i]);
printf("\n");
return 0;
}