Cod sursa(job #294885)

Utilizator DraStiKDragos Oprica DraStiK Data 2 aprilie 2009 20:22:13
Problema Multiplu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <stdio.h>
#define DIM 5000005
struct coada {char c,r,p;} c[DIM];
int ap[DIM],sol[DIM];
int a,b,m;
int euclid (int a,int b)
{
    int r;
    do
    {
        r=a%b;
        a=b;
        b=r;
    }
    while (r);
    return a;
}
void solve ()
{
    int in=1,sf=1,i;
    for (c[in].c=c[in].r=1; in<=sf; ++in)
    {
        if (!ap[(c[in].r*10)%m])
        {
            ap[(c[in].r*10+0)%m]=1;
            c[++sf].c=0;
            c[sf].r=(c[in].r*10)%m;
            c[sf].p=in;
            if(!c[sf].r)
                break;
        }
        if (!ap[(c[in].r*10+1)%m])
        {
            ap[(c[in].r*10+1)%m]=1;
            c[++sf].c=1;
            c[sf].r=(c[in].r*10+1)%m;
            c[sf].p=in;
            if(!c[sf].r)
                break;
        }
    }
    while(sf)
    {
        sol[++sol[0]]=c[sf].c;
        sf=c[sf].p;
    }
    for (i=sol[0]; i; --i)
        printf ("%d",sol[i]);
}
int main ()
{
    freopen ("multiplu.in","r",stdin);
    freopen ("multiplu.out","w",stdout);
    scanf ("%d%d",&a,&b);
    m=a*b/euclid (a,b);
    solve ();
}