Cod sursa(job #130961)

Utilizator raduzerRadu Zernoveanu raduzer Data 2 februarie 2008 18:23:25
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <stdio.h>

int n,m,z,k,r;
int b[2000010];
int a[2000010];
int c[2000010],sol[2000010];

int cmmdc(int a, int b)
{
	int r;
	while (b!=0)
	{
		r=a%b;
		a=b;
		b=r;
	}
	return a;
}


int main()
{
	freopen("multiplu.in","r",stdin);
	freopen("multiplu.out","w",stdout);
	scanf("%d%d",&n,&m);
	int i,j;
	z=(n*m)/cmmdc(n,m);
	a[0]=1;
	a[1]=1;
	b[1]=1;
	printf("1");
	if (z==1) 
	{
		return 0;
	}
	for (i=1; i<=a[0]; ++i)
	{
		if (b[(a[i]*10)%z]==0)
		{
			++a[0];
			a[a[0]]=(a[i]*10)%z;
			c[a[a[0]]]=0;
			b[a[a[0]]]=a[i];
			if ((a[i]*10)%z==0) break;
		}
		if (b[(a[i]*10+1)%z]==0)
		{
			++a[0];
			a[a[0]]=(a[i]*10+1)%z;
			c[a[a[0]]]=1;
			b[a[a[0]]]=a[i];
			if ((a[i]*10+1)%z==0) break;
		}
	}
	k=0;
	r=0;
	while (r!=1)
	{
		k++;
		sol[k]=c[r];
		r=b[r];
	}
	for (i=k; i>0; --i) printf("%d",sol[i]);
	return 0;
}