Cod sursa(job #1699142)

Utilizator raisacmtAxenie Raisa raisacmt Data 6 mai 2016 12:09:00
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <cstdio>

using namespace std;
const int NMAX=2000000;
struct multiplu
{
    int c,r,t;
};
multiplu q[NMAX+5];
bool viz[NMAX+5],sol[NMAX+5];
int main()
{
    freopen("multiplu.in","r",stdin);
    freopen("multiplu.out","w",stdout);
    int a,b,ca,cb,p,u,r,d,ta,k,i;
    scanf("%d%d",&a,&b);
    ca=a;
    cb=b;
    while(b)
    {
        r=a%b;
        a=b;
        b=r;
    }
    d=ca*cb/a;
    a=ca;
    b=cb;
    q[1].c=1;
    q[1].r=1%d;
    q[1].t=0;
    q[0].r=1;
    p=u=1;
    while(p<=u)
    {

        if(viz[(q[p].r*10+0)%d]==0)
        {
             u++;
            q[u].c=0;
            q[u].r=(q[p].r*10+0)%d;
            q[u].t=p;
            viz[q[u].r]=1;

        if(q[u].r==0)
            break;
        }

        if(viz[(q[p].r*10+1)%d]==0)
        {
            u++;
            q[u].c=1;
            q[u].r=(q[p].r*10+1)%d;
            q[u].t=p;
            viz[q[u].r]=1;

        if(q[u].r==0)
            break;
        }
                p++;
}
    ta=q[u].t;k=1;
    sol[1]=q[u].c;
    while(ta!=0)
    {
        sol[++k]=q[ta].c;
        ta=q[ta].t;
    }
    for(i=k; i>=1; i--)
        printf("%d",sol[i]);
    return 0;
}