Cod sursa(job #964911)

Utilizator thewildnathNathan Wildenberg thewildnath Data 22 iunie 2013 18:37:06
Problema Multiplu Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include<stdio.h>

typedef struct tip
{
    int c,r,t;
}tip;

tip v[200012],aux;
char sol[200012],f[200012];

int cmmmc(int a,int b)
{
    int ca=a,cb=b,r;
    while(cb)
    {
        r=ca%cb;
        ca=cb;
        cb=r;
    }
    return a*b/ca;
}

int main()
{
    freopen("multiplu.in","r",stdin);
    freopen("multiplu.out","w",stdout);
    int a,b,m,p,u,c,i;
    scanf("%d%d",&a,&b);
    m=cmmmc(a,b);
    aux.c=1;
    aux.r=aux.c%m;
    aux.t=0;
    p=u=1;
    v[p]=aux;

    while(p<=u)
    {
        if(v[p].r==0)
            break;
        for(c=0;c<=1;++c)
        {
            aux.c=c;
            aux.r=(v[p].r*10+c)%m;
            aux.t=p;
            if(!f[aux.r])
            {
                f[aux.r]=1;
                v[++u]=aux;
            }
        }
        ++p;
    }
    c=0;
    while(p)
    {
        sol[++c]=v[p].c;
        p=v[p].t;
    }
    for(i=c;i>=1;--i)
        printf("%d",sol[i]);
    printf("\n");
    return 0;
}