Cod sursa(job #115827)
#include <stdio.h>
#define mmax 2000005
int a, b, r, M, X, X1, X2, ic, sc;
int E[mmax], C[mmax], R[mmax], U[mmax];
void read()
{
freopen("multiplu.in", "r", stdin);
scanf("%d%d", &a, &b);
}
void solve()
{
M = a * b;
if (M != 1)
while (b)
{
r = a % b;
a = b;
b = r;
}
M /= a;
for (E[1] = C[ic = sc = 1] = R[1] = 1; ic <= sc && !E[0]; ++ic)
{
X = R[ic];
X1 = X * 10 % M;
X2 = (X * 10 + 1) % M;
if (!E[X1])
{
E[X1] = ++sc;
R[sc] = X1;
C[sc] = 0;
U[sc] = ic;
}
if (!E[X2])
{
E[X2] = ++sc;
R[sc] = X2;
C[sc] = 1;
U[sc] = ic;
}
}
}
void back(int k)
{
if (k)
{
back(U[k]);
printf("%d", C[k]);
}
}
void write()
{
freopen("multiplu.out", "w", stdout);
if ( M == 1) printf("1");
else back(E[0]);
printf("\n");
}
int main()
{
read();
solve();
write();
return 0;
}