Cod sursa(job #115793)

Utilizator dominoMircea Pasoi domino Data 16 decembrie 2007 22:51:50
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <stdio.h>

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

int A, B, C, up[MAX_AB], Q[MAX_AB];
char U[MAX_AB], digit[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 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];
        cc = (c*10)%C;
        if (!U[cc])
        {
            U[Q[++qr] = cc] = 1;
            up[cc] = c;
            digit[cc] = 0;
        }
        if (!cc) break;
        cc = (c*10+1)%C;
        if (!U[cc])
        {
           U[Q[++qr] = cc] = 1;
           up[cc] = c;
           digit[cc] = 1;
        }
        if (!cc) break;
    }
    trace(0);

    return 0;
}