Cod sursa(job #173994)

Utilizator marcelcodreaCodrea Marcel marcelcodrea Data 8 aprilie 2008 12:59:13
Problema Multiplu Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include<stdio.h>
int que[2000001],n,m,val,cap,coada,s[2000001];
char rest[2000001],cif[2000001],print[2000001];
int print0;
int val1,val2,k,i;
int cmmdc(int a,int b)
{
     if (b==0) return a;
     cmmdc(b,a%b);
}
int main()
{
   freopen("multiplu.in","r",stdin);
   freopen("multiplu.out","w",stdout);
   scanf("%d %d",&n,&m);
   val=cmmdc(n,m);
   val=n*m/val;
   rest[0]=0;
   rest[1]=1;
   que[1]=1;
   cap=1;
   coada=1;
   while (1)
      {
        val1=(que[cap]*10)%val;
        val2=(val1+1)%val;
        if (rest[val1]==0)
        {
        coada++;
        s[coada]=cap;
        cif[coada]=0;
        que[coada]=val1;
        rest[val1]=1;
        }
        if (rest[0]==1) break;
        if (rest[val2]==0)
        {
        coada++;
        s[coada]=cap;
        cif[coada]=1;
        que[coada]=val2;
        rest[val2]=1;
        }
      if (rest[0]==1) break;
      cap++;
      }
   k=coada;
   while(k!=1)   
     {
      print[print0++]=cif[k];
      k=s[k];
     }
   print[print0++]=1;
   for(i=print0-1;i>=0;i--)
    printf("%d",print[i]);
   return 0;
}