Cod sursa(job #493830)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 19 octombrie 2010 17:35:59
Problema Multiplu Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <cstdio>
#define nmax 200010

int cmmdc(int a, int b)
{
	int k=a%b;
	while (k)
	{
		a=b;
		b=k;
		k=a%b;
	}
	return b;
}

int a, b, h, m, t, q[nmax], v[nmax], s[nmax], d[nmax], f[nmax];

int main()
{
	freopen("multiplu.in","r",stdin);
	freopen("multiplu.out","w",stdout);
	scanf("%d %d",&a,&b);
	int i, c;
	m=a*b/cmmdc(a,b);
	h=1;
	q[1]=v[1]=1;
	for (i=1; ; i++)
	{
		c=q[i]*10%m;
		if (!v[c])
		{
			v[c]=1;
			d[c]=q[i];
			f[c]=0;
			q[++h]=c;
		}
		if (!c) break;
		c=(q[i]*10+1)%m;
		if (!v[c])
		{
			v[c]=1;
			d[c]=q[i];
			f[c]=1;
			q[++h]=c;
		}
		if (!c) break;
	}
	while (d[c])
	{
		s[++t]=f[c];
		c=d[c];
	}
	printf("1");
	if (m>1)
		for (i=t; i>0; i--) printf("%d",s[i]);
}