Cod sursa(job #251818)

Utilizator IoannaPandele Ioana Ioanna Data 3 februarie 2009 13:46:42
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include<stdio.h>
typedef struct {int p,c;long r;}queue;
queue q[2000001];
long a,b,m;
char rest[2000001];
char sol[1000];


void read()
{
scanf("%ld%ld",&a,&b);
}

void cmmmc()
{
long long p;
long r;
p=a*b;
while (b)
      {
       r=a%b;
       a=b;
       b=r;
      }
m=p/a;
}

void numar(int k)
{
int pred;
pred=k;
while (pred)
      {
       sol[++sol[0]]=q[pred].c;
       pred=q[pred].p;
      }
}

void print()
{
int i;
for (i=sol[0];i>=1;i--)
    {
     printf("%d",sol[i]);
    }
printf("\n");
}


int rez()
{
int st,dr;
long r;
st=dr=1;
q[st].c=1;
q[st].p=0;
q[st].r=1%m;
while (1)
      {
        //0
        r=(q[st].r*10)%m;
        if (!rest[r])
           {
            q[++dr].c=0;
            q[dr].p=st;
            q[dr].r=r;
            rest[r]=1;
            if (r==0)
                return dr;
           }
        //1
        r=(q[st].r*10+1)%m;
        if (!rest[r])
           {
            rest[r]=1;
            q[++dr].c=1;
            q[dr].p=st;
            q[dr].r=r;
            if (r==0)
                return dr;
           }
       st++;
      }
      
}



int main()
{
int k;
freopen("multiplu.in","r",stdin);
freopen("multiplu.out","w",stdout);
read();
cmmmc();
k=rez();
numar(k);
print();
return 0;
}