Cod sursa(job #926645)

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

using namespace std;

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

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

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

long gcd (long a, long b){
    long r,Aa=a,Bb=b;
    while(r!=0)
    {
        r=Aa%Bb;
        Aa=Bb;
        Bb=r;
    }
    return Aa;
}
int 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<2;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;
}