Pagini recente » Cod sursa (job #1998937) | Cod sursa (job #2014057) | Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #1006052)
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;
const int NMAX = 2000010;
int Queue[NMAX], Prev[NMAX], D[NMAX], A, B, Front, Back, M;
bool Used[NMAX];
int GCD(int A, int B)
{
if(!B) return A;
return GCD(B, A % B);
}
int LCM(int A, int B)
{
return (A * B) / GCD(A, B);
}
void Reconstr(int Pos)
{
if(Pos == -1) return ;
Reconstr(Prev[Pos]);
printf("%i", D[Pos]);
}
int main()
{
freopen("multiplu.in", "r", stdin);
freopen("multiplu.out", "w", stdout);
scanf("%i %i", &A, &B);
M = LCM(A, B);
Queue[Front = Back = 1] = 1;
Prev[1] = -1;
D[1] = 1;
Used[1] = 1;
while(Back <= M)
{
int Rest = Queue[Front];
if(Rest == 0)
{
Reconstr(Front);
return 0;
}
if(!Used[(Rest * 10) % M])
{
Queue[++Back] = (Rest * 10) % M;
Used[(Rest * 10) % M] = 1;
Prev[Back] = Front;
D[Back] = 0;
}
if(!Used[(Rest * 10 + 1) % M])
{
Queue[++Back] = (Rest * 10 + 1) % M;
Used[(Rest * 10 + 1) % M] = 1;
Prev[Back] = Front;
D[Back] = 1;
}
Front ++;
}
return 0;
}