Cod sursa(job #115934)

Utilizator MariusMarius Stroe Marius Data 17 decembrie 2007 13:56:54
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <cstdio>
#include <queue>

using namespace std;


const char iname[] = "multiplu.in";
const char oname[] = "multiplu.out";

#define MAXM  2000005

queue <int> Q;

bool sel[MAXM];

int  rest[MAXM], cifra[MAXM];


void print(int r) {
	if (r != 1)	print(rest[r]);
	printf("%d", cifra[r]);
}

int gcd(int a, int b) {
	if (!b)  return a;
	return gcd(b, a % b);
}

int main(void)
{
	freopen(iname, "r", stdin);
	freopen(oname, "w", stdout);

	int A, B;
	scanf("%d %d", &A, &B);
	int M = A * B / gcd(A, B);

	sel[1] = true;
	cifra[1] = 1;
	for (Q.push(1); !Q.empty(); Q.pop())
	{
		int X = Q.front();
		if (X == 0) {
			print(0);
			return 0;
		}
		int r = (X * 10) % M;
		if (!sel[r]) 
		{
			Q.push(r);
			sel[r] = true;
			rest[r] = X;
			cifra[r] = 0;
		}
		r = (X * 10 + 1) % M;
		if (!sel[r]) 
		{
			Q.push(r);
			sel[r] = true;
			rest[r] = X;
			cifra[r] = 1;
		}
	}
	
	return 0;
}