Pagini recente » Cod sursa (job #1316487) | Cod sursa (job #128609) | Cod sursa (job #1068210) | Cod sursa (job #3179728) | Cod sursa (job #115672)
Cod sursa(job #115672)
#include <cstdio>
#include <queue>
using namespace std;
#define MAXN 2000005
int A, B, M;
char seen[MAXN]; int p[MAXN];
queue<int> Q;
inline int gcd( int A, int B )
{
int C;
for (; A % B; )
{
C = A % B;
A = B;
B = C;
}
return B;
}
inline void genSol( int k )
{
if (k == 1) { printf("1"); return; }
genSol( p[k] );
if ((p[k] * 10) % M == k)
printf("0");
else
printf("1");
}
int main()
{
freopen("multiplu.in", "rt", stdin);
freopen("multiplu.out", "wt", stdout);
scanf("%d %d", &A, &B);
M = A * B / gcd(A, B);
seen[1] = 1;
for (Q.push(1); !Q.empty(); Q.pop())
{
int i = Q.front(), newi;
if (i == 0)
{
genSol(i);
printf("\n");
return 0;
}
newi = (i * 10) % M;
if (!seen[newi])
seen[newi] = 1,
p[newi] = i,
Q.push( newi );
newi = (i * 10 + 1) % M;
if (!seen[newi])
seen[newi] = 1,
p[newi] = i,
Q.push( newi );
}
return 0;
}