Cod sursa(job #489484)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 2 octombrie 2010 18:51:34
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include<cstdio>
int a,b,cif[1<<21],lastr[1<<21],s[1<<21],poz[1<<21];
bool f[1<<21];
int cmmdc(int x,int y)
{
    int r=x%y;
    while(r)
    {
        x=y;
        y=r;
        r=x%y;
    }
    return y;
}
int cmmmc(int x,int y)
{
    return x/cmmdc(x,y)*y;
}
void afis(int rest)
{
    if(lastr[poz[rest]]!=-1)
        afis(lastr[poz[rest]]);
    printf("%d",cif[poz[rest]]);
}
void solve()
{
    int m=cmmmc(a,b);
    int q=0;
    s[++q]=1;
    cif[q]=1;
    lastr[q]=-1;
    f[1]=true;
    poz[1]=1;
    for(int i=1;i<=q;i++)
    {
        if(!f[(s[i]*10)%m])
            s[++q]=(s[i]*10)%m, cif[q]=0, lastr[q]=s[i], f[(s[i]*10)%m]=true, poz[(s[i]*10)%m]=q;
        if(f[0])
            break;
        if(!f[(s[i]*10+1)%m])
            s[++q]=(s[i]*10+1)%m, cif[q]=1, lastr[q]=s[i], f[(s[i]*10+1)%m]=true, poz[(s[i]*10+1)%m]=q;
        if(f[0])
            break;
    }
    afis(0);
}
int main()
{
    freopen("multiplu.in","r",stdin);
    freopen("multiplu.out","w",stdout);
    scanf("%d%d",&a,&b);
    solve();
    return 0;
}