Cod sursa(job #1332889)

Utilizator zhm248Mustatea Radu zhm248 Data 2 februarie 2015 15:55:31
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include<cstdio>
using namespace std;
int cmmdc(int a,int b)
{
    while(b!=0)
    {
        int r=a%b;
        a=b;
        b=r;
    }
    return a;
}

int cmmmc(int a,int b)
{
    return (a*b)/cmmdc(a,b);
}

struct Doi
{
    bool c;
    int r,t;
};

Doi q[2000005];
int sol[150005],f[2000005];
int main()
{
    freopen("multiplu.in","r",stdin);
    freopen("multiplu.out","w",stdout);
    int a,b,x,i,ultim=1,j,nr=0,ok=1;
    scanf("%d%d",&a,&b);
    x=cmmmc(a,b);
    q[1].c=1;
    q[1].r=1;
    q[1].t=0;
    for(i=1;i<=ultim;++i)
    {
        if(q[i].r==0)
        {
            j=i;
            while(ok!=0)
            {
                sol[++nr]=q[j].c;
                j=q[j].t;
                if(j==0)
                ok=0;
            }
            for(j=nr;j>=1;--j)
            {
                printf("%d",sol[j]);
            }
            break;
        }
        else
        {
            if(f[(q[i].r*10)%x]==0)
            {
            q[++ultim].c=0;
            q[ultim].r=(q[i].r*10)%x;
            q[ultim].t=i;
            f[q[ultim].r]=1;
            }
            if(f[((q[i].r*10)+1)%x]==0)
            {
            q[++ultim].c=1;
            q[ultim].r=((q[i].r*10)+1)%x;
            q[ultim].t=i;
            f[q[ultim].r]=1;
            }
        }
    }
    return 0;
}