Cod sursa(job #129274)

Utilizator victorsbVictor Rusu victorsb Data 28 ianuarie 2008 21:03:44
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <cstdio>

#define Nmax 2000015
#define Lmax 1024

int a, b, m;
int d[Nmax];
int r[Lmax];
int v[Lmax];

void citire()
{
	scanf("%d %d\n", &a, &b);
}

int gcd(int a, int b)
{
	int c;

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

	return a;
}

void solve()
{
	int i, j, rest, next, cf = 0;
	
	m = a * b / gcd(a, b);

	for (i = 0; i < m; ++i)
		d[i] = -1;

	d[1] = 0;
	r[0] = rest = 1;
	for (i = 1; d[0] == -1; ++i)
	{
		r[i] = rest = (rest * 10) % m;
		next = rest;
		if (d[next] == -1) d[next] = i;
		for (j = 0; j < m; ++j, ++next)
		{
			if (next == m) next -= m;
			if (d[j] != -1 && d[j] != i && d[next] == -1) d[next] = i;
		}
	}      

	i = 0;
	do
	{
		if (d[i] > cf) cf = d[i];

		v[d[i]] = 1;
		i -= r[d[i]];
		if (i < 0) i += m;
		++j;
	}
	while (i != 0);

	for (i = cf; i >= 0; --i)
		printf("%d", v[i]);
	printf("\n");
}

int main()
{
	freopen("multiplu.in", "r", stdin);
	freopen("multiplu.out", "w", stdout);
	
	citire();
	solve();

	return 0;
}