Cod sursa(job #760213)

Utilizator geniucosOncescu Costin geniucos Data 20 iunie 2012 16:39:39
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include<cstdio>
#include<queue>
using namespace std;
int nr,ul,x,v,a1,b1,i,p,j,r,a[2000002],b[2000002],c[2000002],ras[2000002];
queue < int > cc;
int main()
{
freopen("multiplu.in","r",stdin);
freopen("multiplu.out","w",stdout);
scanf("%d",&a1);
scanf("%d",&b1);
r=0;
p=a1*b1;
while(b1!=0)
{
	r=a1%b1;
	a1=b1;
	b1=r;
}
p=p/a1;
v=p;
a[1]=1;
b[1]=1;
c[1]=0;
cc.push(1);
while(!cc.empty())
{
	x=cc.front();
	for(i=0;i<=1;i++)
	{
		if(a[(x*10+i)%v]==0)
		{
			a[(x*10+i)%v]=a[x]+1;
			b[(x*10+i)%v]=i;
			c[(x*10+i)%v]=x;
			cc.push((x*10+i)%v);
		}
		if(a[0]!=0) break;
	}
	if(i<=1) break;
	cc.pop();
}
//printf("%d\n",a[0]);
ul=0;
nr=a[0];
while(1)
{
	ras[nr]=b[ul];
	ul=c[ul];
	nr--;
	if(ul==0) break;
}
for(i=1;i<=a[0];i++)
	printf("%d",ras[i]);
return 0;
}