Cod sursa(job #1226127)

Utilizator mihaimusatMihai Musat mihaimusat Data 4 septembrie 2014 17:06:22
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <cstdio>

using namespace std;

#define NMAX 2000005

int a,b,m,i,k,r;
int x[NMAX],y[NMAX],z[NMAX],sol[NMAX];

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",&a,&b);
	m=(a*b)/cmmdc(a,b);
	x[0]=1;
	x[1]=1;
	y[1]=1;
	printf("1");
	if (m==1)
	{
		return 0;
	}
	for (i=1;i<=x[0];++i)
	{
		if (y[(x[i]*10)%m]==0)
		{
			++x[0];
			x[x[0]]=(x[i]*10)%m;
			z[x[x[0]]]=0;
			y[x[x[0]]]=x[i];
			if ((x[i]*10)%m==0) break;
		}
		if (y[(x[i]*10+1)%m]==0)
		{
			++x[0];
			x[x[0]]=(x[i]*10+1)%m;
			z[x[x[0]]]=1;
			y[x[x[0]]]=x[i];
			if ((x[i]*10+1)%m==0) break;
		}
	}
	k=0;
	r=0;
	while(r!=1)
	{
		k++;
		sol[k]=z[r];
		r=y[r];
	}
	for (i=k;i>0;--i)
        printf("%d",sol[i]);
	return 0;
}