Cod sursa(job #115488)

Utilizator alextheroTandrau Alexandru alexthero Data 16 decembrie 2007 12:49:58
Problema Multiplu Scor 100
Compilator cpp Status done
Runda preONI 2008, Runda 2, Clasa a 10-a Marime 1.01 kb
#include <stdio.h>
#include <string>

#define nmax 2000000

using namespace std;

int a, b, n, p, q, newrest;
int prev[nmax], st[nmax];

int gcd(int a, int b)
{
	if(b == 0) return a;
	else return gcd(b, a % b);
}

int cmmmc(int a, int b)
{
	return a * b / gcd(a, b);
}

void bfs()
{
	p = q = 1;
	memset(prev, -1, sizeof(prev));
	prev[1] = -2;
	st[p] = 1;
	while(q <= p)
	{
		newrest = st[q] * 10 % n;
		if(prev[newrest] == -1)
		{
			st[++p] = newrest;
			prev[newrest] = st[q];
		}
		if(st[p] == 0) return ;

		newrest = (st[q] * 10 + 1) % n;
		if(prev[newrest] == -1)
		{
			st[++p] = newrest;
			prev[newrest] = st[q];
		}
		if(st[p] == 0) return ;
		q++;
	}
}

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

	scanf("%d%d", &a, &b);
	n = cmmmc(a, b);

	bfs();
	string s = "";
	int crt = 0;

	while(prev[crt] != -2) 
	{
		if(prev[crt] * 10 % n == crt) s += '0';
		else s += '1';
		crt = prev[crt];
	}
	s += '1';

	reverse(s.begin(), s.end());
	printf("%s\n", s.c_str());

	return 0;
}