Cod sursa(job #244073)

Utilizator GheorgheMihaiMihai Gheorghe GheorgheMihai Data 14 ianuarie 2009 16:10:38
Problema Multiplu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include<stdio.h>
struct QUEUE
{
char c;
long r;
long p;
};
QUEUE q[2000002];
long rest[2000002];
long i,nr,d,u,p;
char a[2000002];
long A,B,n;
long cmmmc(long A,long B)
{
  long x,y,r;
  x=A;
  y=B;
  r=A%B;
  while(r)
  {
	x=y;
	y=r;
	r=x%y;
  }
  return (A*B)/y;
}
int main()
{
	freopen("multiplu.in","r",stdin);
	freopen("multiplu.out","w",stdout);

	scanf("%ld%ld",&A,&B);
	n=cmmmc(A,B);

	q[1].c=1;
	q[1].r=1;
	q[1].p=0;
	p=u=1;
	while(q[p].r!=0)
	{
	   for(d=0;d<=1;++d)
	   {
		 if(rest[(q[p].r*10+d)%n]==0)
		 {
		   rest[(q[p].r*10+d)%n]=1;
		   u++;
		   q[u].c=d;
		   q[u].r=(q[p].r*10+d)%n;
		   q[u].p=p;
		 }

	   }
	   p++;
	}

	while(p)
	{
	  nr++;
	  a[nr]=q[p].c;
	  p=q[p].p;
	}
	for(i=nr;i>=1;--i)
	  printf("%ld",a[i]);
	printf("\n");
	return n;
}