Cod sursa(job #115827)

Utilizator vlad.maneaVlad Manea vlad.manea Data 16 decembrie 2007 23:52:06
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <stdio.h>

#define mmax 2000005

int a, b, r, M, X, X1, X2, ic, sc;

int E[mmax], C[mmax], R[mmax], U[mmax];

void read()
{
	freopen("multiplu.in", "r", stdin);

	scanf("%d%d", &a, &b);
}

void solve()
{
	M = a * b;

	if (M != 1)

	while (b)
	{
		r = a % b;
		a = b;
		b = r;
	}

	M /= a;

	for (E[1] = C[ic = sc = 1] = R[1] = 1; ic <= sc && !E[0]; ++ic)
	{
		X = R[ic];
		X1 = X * 10 % M;
		X2 = (X * 10 + 1) % M;

		if (!E[X1])
		{
			E[X1] = ++sc;
			R[sc] = X1;
			C[sc] = 0;
			U[sc] = ic;
		}

		if (!E[X2])
		{
			E[X2] = ++sc;
			R[sc] = X2;
			C[sc] = 1;
			U[sc] = ic;
		}
	}

}

void back(int k)
{
	if (k)
	{
		back(U[k]);

		printf("%d", C[k]);
	}
}

void write()
{
	freopen("multiplu.out", "w", stdout);

	if ( M == 1) printf("1");

	else back(E[0]);

	printf("\n");
}

int main()
{
	read();

	solve();

	write();

	return 0;
}