Cod sursa(job #1699144)

Utilizator VAIonescuIonescu Vlad-Andrei VAIonescu Data 6 mai 2016 12:29:28
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <cstdio>
using namespace std;

const int NMAX = 2000000;

struct Multiplu
{
    bool c;
    int r,t;
}q[NMAX+1];
bool viz[NMAX+1];
bool sol[NMAX+1];

int cmmdc(int a,int b){
    int c;
    while (b){
        c=a%b;
        a=b;
        b=c;
    }
    return a;
}

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

int main()
{
    freopen("multiplu.in","r",stdin);
    freopen("multiplu.out","w",stdout);
    int a,b,r,p=1,u=1;
    long long m;
    scanf("%d%d",&a,&b);
    m=cmmmc(a,b);
    q[u].c=1;
    q[u].r=1;
    q[u].t=0;
    while (p<=u)
    {
        r=(q[p].r*10+0)%m;
        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)%m;
        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++;
    }
    a=0;
    sol[++a]=q[u].c;
    for (int i=q[u].t;i>0;i=q[i].t)
    {
        sol[++a]=q[i].c;
    }
    b=(a+1)>>1;
    for (int i=1;i<=b;i++)
    {
        p=sol[i];
        sol[i]=sol[a-i+1];
        sol[a-i+1]=p;
    }
    for (int i=1;i<=a;i++)
    {
        printf("%d",sol[i]);
    }
    return 0;
}