Cod sursa(job #114802)

Utilizator dominoMircea Pasoi domino Data 15 decembrie 2007 22:39:36
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, T[MAX_AB][2], 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(T[c][0]);
    printf("%d", T[c][1]);
}

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)
    {
        c = Q[ql];
        if (!c) break;
        for (i = 0; i < 2; ++i)
        {
           cc = (c*10+i)%C;
           if (U[cc]) continue;
           U[cc] = 1;
           T[cc][0] = c; 
           T[cc][1] = i;
           Q[++qr] = cc;
        }
    }
    trace(0);

    return 0;
}