Cod sursa(job #116309)

Utilizator MarquiseMarquise Marquise Data 18 decembrie 2007 13:48:32
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <stdio.h>
#define NMAX 2000000
int a, b, m, c;
int  viz[250000];
typedef struct
{
    char c;
    int r, p;
}QUADA;
QUADA q[NMAX];

int cmmdc(int a, int b)
{
    int r;
    while (b)
    {
        r = a %b;
        a = b;
        b = r;
    }
    return a;
}

void afisare(int i)
{
    if (i!=0)
    {
        afisare(q[i].p);
        printf("%c",q[i].c);
    }
}

void rezolv()
{
    int st, dr, ex = 1, r;
    st = dr = 1;
    q[st].c = '1';
    q[st].p = 0;
    q[st].r = 1 % m;
    viz[q[st].r>>3] |=(1<<(q[st].r&7));
    while ( st <= dr && ex)
    {
        r = (q[st].r*10 ) % m;
        if ( !(viz[r>>3] & (1<<(r&7)) ) )
        {
            dr++;
            q[dr].r = r;
            q[dr].p = st;
            q[dr].c = '0';
            viz[q[dr].r>>3] |= 1<<(q[dr].r&7);
            if (q[dr].r == 0)
               ex = 0;
        }
        if ( ex)
        {
        r = (q[st].r*10 + 1) % m;
        if ( !(viz[r>>3] & (1<<(r&7)) ) )
        {
            dr++;
            q[dr].r = r;
            q[dr].p = st;
            q[dr].c = '1';
            viz[q[dr].r>>3] |= 1<<(q[dr].r&7);
            if (q[dr].r == 0)
               ex = 0;
        }
        }
        st++;
    }

    if ( !ex)
       afisare(dr);


}


int main()
{
    freopen("multiplu.in", "r", stdin);
    freopen("multiplu.out", "w", stdout);
    scanf("%d %d", &a, &b);
    c = cmmdc(a,b);
    m = (a*b)/c;
    rezolv();
    return 0;
}