Cod sursa(job #244052)

Utilizator GheorgheMihaiMihai Gheorghe GheorgheMihai Data 14 ianuarie 2009 15:48:05
Problema Multiplu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include<stdio.h>
struct gigel
{
 long c,r,prec;
};

gigel q[2000301];
char f[2000001];
int x[20000];

long cmmdc(long n,long m)
{
  long r;
  while(m)
   {
    r=n%m;
    n=m;
    m=r;
   }

return n;
}

int main()
{
long i,n,m,k,N,p,u;

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

   scanf("%ld%ld",&n,&m);

   k=cmmdc(n,m);
   N=n*m/k;

   if (N==1) printf("%ld ",1);
    else
      {
       p=u=1;
       q[1].c=1;
       q[1].r=1;
       q[1].prec=0;

       while(p<=u&&q[p].r!=0)
        {
          u++;
          q[u].c=0;
          q[u].r=(q[p].r*10)%N;
          q[u].prec=p;
          if (f[q[u].r]==1) u--; else f[q[u].r]=1;

          u++;
          q[u].c=1;
          q[u].r=(q[p].r*10+1)%N;
          q[u].prec=p;
          if (f[q[u].r]==1) u--; else f[q[u].r]=1;
          p++;

        }

      }


  i=p;
  u=0;
  while(i!=0)
   {
     x[++u]=q[i].c;
     i=q[i].prec;
   }

  for (i=1;i<=u;i++)
   printf("%d",x[i]);

return 0;
}