Cod sursa(job #174590)

Utilizator marcelcodreaCodrea Marcel marcelcodrea Data 8 aprilie 2008 23:53:39
Problema Multiplu Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include<stdio.h>   
int que[2000001],n,m,val,cap,coada,s[2000001];   
char rest[2000001],cif[2000001],pt[2000001];
int pt0;   
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)      
     {   
      pt[pt0++]=cif[k];   
      k=s[k];   
     }   
   pt[pt0++]=1;
   for(i=pt0-1;i>=0;i--)   
    printf("%d",pt[i]);
   return 0;   
}