Cod sursa(job #115671)

Utilizator sealTudose Vlad seal Data 16 decembrie 2007 19:55:48
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include<stdio.h>
#define Nm (1<<21)
char Ans[Nm];
int Q[Nm],Pre[Nm],n,m;

void read()
{
    freopen("multiplu.in","r",stdin);
    scanf("%d%d",&n,&m);
}

int gcd(int a, int b)
{
    int r;

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

void solve()
{
    char c;
    int l,r,x,y;

    n=n*m/gcd(n,m);
    Q[l=r=0]=1;
    Pre[1]=1;

    while(!Pre[0])
    {
        x=Q[l++];
        y=x*10%n;
        if(!Pre[y])
        {
            Pre[y]=x;
            Q[++r]=y;
        }
        y=(y+1)%n;
        if(!Pre[y])
        {
            Pre[y]=x;
            Q[++r]=y;
        }
    }

    x=l=r=0;
    while(x!=1)
    {
        if(Pre[x]*10%n==x)
            Ans[r++]='0';
        else
            Ans[r++]='1';
        x=Pre[x];
    }
    Ans[r]='1';
    while(l<r)
    {
        c=Ans[l];
        Ans[l]=Ans[r];
        Ans[r]=c;
        ++l; --r;
    }
}

void write()
{
    freopen("multiplu.out","w",stdout);
    printf("%s\n",Ans);
}

int main()
{
    read();
    solve();
    write();
    return 0;
}