Cod sursa(job #1827533)

Utilizator mara.priponMara Pripon mara.pripon Data 11 decembrie 2016 21:58:36
Problema Multiplu Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <cstdio>

using namespace std;
const int NMAX=2000000;
struct MULTIPLU
{
    int c,r,t;
};
MULTIPLU q[NMAX+5];
bool fr[NMAX+5],sol[NMAX+5];
int main()
{
    freopen ("multiplu.in","r",stdin);
    freopen ("multiplu.out","w",stdout);
    int a,b,m,p,u,ca,cb,rn,r,k,i;
    scanf ("%d%d",&a,&b);
    ca=a;
    cb=b;
    while (b) {
        r=a%b;
        a=b;
        b=r;
    }
    m=ca*cb/a;
    p=u=1;
    MULTIPLU temp;
    temp.c=1; temp.r=1; temp.t=0; fr[1]=1;
    q[u]=temp;
    if (m==1)
        printf ("1");
    else {
    while (p<=u) {
        //Se ADAUGA CIFRA 0
        rn=(q[p].r*10+0)%m;
        if (fr[rn]==0) {
            fr[rn]=1;
            temp.c=0; temp.r=rn; temp.t=p;
            q[++u]=temp;
            if (rn==0)
                break;
        }
        //Se adauga cifra 1
        rn=(q[p].r*10+1)%m;
        if (fr[r]==0) {
            fr[rn]=1;
            temp.c=1; temp.r=rn; temp.t=p;
            q[++u]=temp;
            if (rn==0)
                break;
        }

        p++;

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