Cod sursa(job #1700075)

Utilizator vladcainamisirVlad Cainamisir vladcainamisir Data 9 mai 2016 12:33:37
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
{
    bool c;
    int r,t;
};
multiplu q[NMAX+5];
bool viz[NMAX+5];
bool sol[NMAX+5];
int main()
{
    freopen("multiplu.in","r",stdin);
    freopen("multiplu.out","w",stdout);
    int a,b,ca,cb,r,d,p,u,i,ta,k;
    scanf("%d%d",&a,&b);
    ca=a;
    cb=b;
    //Facem CMMDC
    while(b)
    {
        r=a%b;
        a=b;
        b=r;
    }
    d=ca*cb/a;//CMMMC
    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)
    {
        r=(q[p].r*10+0)%d;
        if(viz[r]==0)
        {
            ++u;viz[r]=1;
            q[u].c=0;
            q[u].r=r;
            q[u].t=p;
        if(r==0)
            break;
        }
         r=(q[p].r*10+1)%d;
        if(viz[r]==0)
        {
            u++;
            q[u].c=1;
            q[u].r=r;
            q[u].t=p;
            viz[r]=1;
        if(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;
}