Cod sursa(job #961200)
#include <fstream>
using namespace std;
long A,B,C;
long cmmdc(long a,long b)
{
while (b != 0)
{
long c = a % b;
a = b;
b = c;
}
return a;
}
long cmmmc(long a,long b)
{
return a * b / cmmdc(a,b);
}
long Cifre[2000005];
long Prev[2000005];
long Queue[2000005];
long PushPos;
long PopPos;
char Rez[2000005];
long RezLen = 0;
void Push(long a)
{
Queue[PushPos] = a;
PushPos += 1;
}
long Pop(void)
{
PopPos += 1;
return Queue[PopPos - 1];
}
long Empty(void)
{
return PushPos == PopPos;
}
int main(void)
{
fstream fin("multiplu.in",ios::in);
fstream fout("multiplu.out",ios::out);
fin >> A >> B;
C = cmmmc(A,B);
Cifre[1] = 1;
Prev[1] = -1;
PushPos = 0;
PopPos = 0;
Push(1);
while (Empty() == 0)
{
long v = Pop();
if (v == 0)
{
RezLen = 0;
while (Prev[v] != 0)
{
Rez[RezLen] = Cifre[v] + '0';
RezLen += 1;
v = Prev[v];
}
for (long a = RezLen - 1;a >= 0;a -= 1)
{
fout << Rez[a];
}
break;
}
long v1,v2;
v1 = (v * 10 + 0) % C;
v2 = (v * 10 + 1) % C;
if (Prev[v1] == 0)
{
Prev[v1] = v;
Cifre[v1] = 0;
Push(v1);
}
if (Prev[v2] == 0)
{
Prev[v2] = v;
Cifre[v2] = 1;
Push(v2);
}
}
fin.close();
fout.close();
return 0;
}