Cod sursa(job #129520)

Utilizator raduzerRadu Zernoveanu raduzer Data 29 ianuarie 2008 17:27:14
Problema Multiplu Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <stdio.h>

int n,m,z;
int a[2000010],b[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;
	if (z==1) 
	{
		printf("1\n");
		return 0;
	}
	for (i=1; i<=a[0]; ++i)
	{
		if ((a[i]*10)%z==0)
		{
			printf("%d",a[i]*10);
			return 0;
		}
		if (b[(a[i]*10)%z]==0) 
		{
			b[(a[i]*10)%z]++;
			++a[0];
			a[a[0]]=a[i]*10;
		}
		if ((a[i]*10+1)%z==0)
		{
			printf("%d",a[i]*10+1);
			return 0;
		}
		if (b[(a[i]*10+1)%z]==0) 
		{
			b[(a[i]*10+1)%z]++;
			++a[0];
			a[a[0]]=a[i]*10+1;
		}
	}
	return 0;
}