Cod sursa(job #1389016)

Utilizator robertstrecheStreche Robert robertstreche Data 15 martie 2015 21:21:53
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <stdio.h>
#define NMax 2000005

int a,b,cmmmc;
int q[NMax], up[NMax];
char digit[NMax], uz[NMax];

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

int main(void)
{
    int i,ql=0,qr=0,x;

    freopen("multiplu.in","r",stdin);
    freopen("multiplu.out","w",stdout);

    scanf("%d %d",&a,&b);
    cmmmc=a*b/gcd(a,b);

    for (q[0]=1,digit[0]=1,up[0]=-1,uz[1]=1;qr<=ql;qr++)
    {
        x = (q[qr] * 10) % cmmmc;
        if (!uz[x])
            q[++ql]=x,uz[x]=1,up[ql]=qr,digit[ql]=0;

        x = (q[qr]*10+1)%cmmmc;
        if (!uz[x])
            q[++ql]=x,uz[x]=1,up[ql]=qr,digit[ql]=1;

        if (uz[0])
            break;
    }


    for (x=ql-(q[ql]!=0),ql=0;x!=-1;x=up[x])
        q[++ql]=(int)digit[x];

    for (i = ql;i>= 1;i--)
        printf("%d",q[i]);
    printf("\n");

    return 0;
}