Pagini recente » Cod sursa (job #742156) | Cod sursa (job #1826598) | Cod sursa (job #1929392) | Cod sursa (job #1161263) | Cod sursa (job #1802700)
#include <cstdio>
#include <queue>
using namespace std;
const int NMAX = 2000000;
queue <int> q; int sol[NMAX + 5];
int viz[NMAX + 5];
int last[NMAX + 5];
int cif[NMAX + 5];
int cmmdc(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, ans, aux, nou;
scanf("%d %d", &a, &b);
ans = a * b / cmmdc(a, b);
if (ans <= 1)
{
printf("%d\n", ans);
return 0;
}
q.push(1); viz[1] = 1;
last[1] = -1; cif[1] = 1;
while (!q.empty())
{
aux = q.front();
if (aux == 0)
break;
/// adaugam 0 ///
nou = (aux * 10 + 0) % ans;
if (viz[nou] == 0)
{
viz[nou] = 1;
last[nou] = aux;
cif[nou] = 0;
q.push(nou);
}
/// adaugam 1 ///
nou = (aux * 10 + 1) % ans;
if (viz[nou] == 0)
{
viz[nou] = 1;
last[nou] = aux;
cif[nou] = 1;
q.push(nou);
}
q.pop();
}
int nr = 0;
while (aux != -1)
{
sol[++nr] = cif[aux];
aux = last[aux];
}
for (; nr > 0; --nr)
printf("%d", sol[nr]);
return 0;
}