Cod sursa(job #161232)

Utilizator rethosPaicu Alexandru rethos Data 17 martie 2008 19:32:41
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <stdio.h>
#define NM 2000001
char viz[NM];
long c[NM];
long prev[NM],cif[NM];
long a,b,cm,m,st,dr;
long cmmdc(long x,long y)
{long r=x%y;
 while (r)
   {x=y;
    y=r;
    r=x%y;
   }
 return y;
}
void scrie(long k)
{if(prev[k]) scrie(prev[k]);
 printf("%ld",cif[k]);
}
int main()
{freopen("multiplu.in","r",stdin);
 freopen("multiplu.out","w",stdout);
 scanf("%ld %ld",&a,&b);
 long rest,i;
 cm=cmmdc(a,b);
 m=(a*b)/cm;
 c[1]=1;
 prev[1]=0;
 cif[1]=1;
 st=1,dr=1;
 for (i=1;i<=m;i++) viz[i]=0;
 viz[1%m]=1;
 while(st<=dr)
   {rest=(c[st]*10)%m;
    if(viz[rest]==0)
      {c[++dr]=rest;
       prev[dr]=st;
       cif[dr]=0;
       viz[rest]=1;
       if(rest==0)
         {scrie(dr);
          return 0;
         }
      }
    rest=(c[st]*10+1)%m;
    if(viz[rest]==0)
      {c[++dr]=rest;
       prev[dr]=st;
       cif[dr]=1;
       viz[rest]=1;
       if(rest==0)
         {scrie(dr);
          return 0;
         }
      }
    st++;
   }
 return 0;
}