Cod sursa(job #114803)

Utilizator dominoMircea Pasoi domino Data 15 decembrie 2007 22:41:25
Problema Multiplu Scor Ascuns
Compilator cpp Status done
Runda Marime 0.85 kb
#include <stdio.h>

#define MAX_AB 2000005
#define FIN "multiplu.in"
#define FOUT "multiplu.out"

int A, B, C, up[MAX_AB], digit[MAX_AB], Q[MAX_AB];
char U[MAX_AB];

int gcd(int a, int b) { return !b ? a : gcd(b, a%b); }

void trace(int c)
{
    if (c == 1) { printf("1"); return; }
    trace(up[c]);
    printf("%d", digit[c]);
}

int main(void)
{
    int i, c, cc, ql, qr;

    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);

    scanf("%d %d", &A, &B);
    C = A*B/gcd(A, B);

    for (U[Q[ql = qr = 0] = 1] = 1; ql <= qr; ++ql)
    {
        if (!(c = Q[ql])) break;
        for (i = 0; i < 2; ++i)
        {
           cc = (c*10+i)%C;
           if (U[cc]) continue;
           U[cc] = 1;
           up[cc] = c;
           digit[cc] = i;
           Q[++qr] = cc;
        }
    }
    trace(0);

    return 0;
}