Cod sursa(job #926628)

Utilizator stefan.friptuPetru Stefan Friptu stefan.friptu Data 25 martie 2013 12:04:51
Problema Multiplu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <cstdio>

using namespace std;

struct tip{
    long c,r,t;
};

tip aux,q[2000010];
bool f[2000010];
char rez[2000010];

long a,b,c,u,p,CM,i,n;

long gcd (long a, long b){
    long r;
    while(r!=0)
    {
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}
long main () {

    freopen("multiplu.in","r",stdin);
    freopen("multiplu.out","w",stdout);

    scanf("%ld%ld",&a,&b);

    long CM=(a*b)/gcd(a,b);
    p=u=1;
    aux.c=1,aux.r=(aux.c)%CM,aux.t=0;
    q[p]=aux;
    while(p<=u)
    {
        if(q[p].r==0)
            break;
        for(c=0;c<=1;c++)
        {
            aux.c=c;
            aux.r=(q[p].r*10+c)%CM;
            aux.t=p;
            if(!f[aux.r])
            {
                f[aux.r]=1;
                q[++u]=aux;
            }

        }
        p++;
    }
    c=0;
    while(p)
    {
        rez[++c]=q[p].c;
        p=q[p].t;
    }
    for(i=c;i>=1;i--)
        printf("%ld",rez[i]);
    printf("\n");
    return 0;
}