Cod sursa(job #291234)

Utilizator 630r63Ilinca George Mihai 630r63 Data 29 martie 2009 16:11:54
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include<stdio.h>
struct COADA
{ char c; long r,p;};
long cmmdc(long a,long b)
 {
  long r;
  while(b!=0)
   {
    r=a%b;
    a=b;
    b=r;
   }
  return a;
 }
long i,a,b,u,p,cmmmc;
char viz[2000002];
COADA q[2000002];
int main()
{
 char sol[2000002];
 freopen("multiplu.in","r",stdin);
 freopen("multiplu.out","w",stdout);
 scanf("%ld%ld",&a,&b);
 cmmmc=(a*b)/cmmdc(a,b);
 p=u=1;
 q[1].c=1;
 q[1].r=1;
 q[1].p=0;
 while(p<=u)
  {
   if(viz[(q[p].r*10+0)%cmmmc]==0)
   {
    viz[(q[p].r*10+0)%cmmmc]=1;
    u++;
    q[u].c=0;
    q[u].r=(q[p].r*10+0)%cmmmc;
    q[u].p=p;
    if(q[u].r==0)
	break;
   }
   if(viz[(q[p].r*10+1)%cmmmc]==0)
   {
    viz[(q[p].r*10+1)%cmmmc]=1;
    u++;
    q[u].c=1;
    q[u].r=(q[p].r*10+1)%cmmmc;
    q[u].p=p;
    if(q[u].r==0)
	break;
   }
    p++;
  }
 sol[0]=0;
 while(u!=0)
  {
   sol[++sol[0]]=q[u].c;
   u=q[u].p;
  }
 for(i=sol[0];i>=1;i--)
  printf("%d",sol[i]);
 return 0;
}