Cod sursa(job #115930)

Utilizator MariusMarius Stroe Marius Data 17 decembrie 2007 13:48:24
Problema Multiplu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <cstdio>
#include <queue>

using namespace std;


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

#define MAXM  2000005

int queue[MAXM];

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);
	
	int head, tail;

	sel[1] = true;
	cifra[1] = 1;
	for (queue[head = tail = 0] = 1; head <= tail; ++ head)
	{
		int X = queue[head];
		int r = (X * 10) % M;
		if (!sel[r]) 
		{
			queue[++ tail] = r;
			sel[r] = true;
			rest[r] = X;
			cifra[r] = 0;
		}
		r = (X * 10 + 1) % M;
		if (!sel[r]) 
		{
			queue[++ tail] = r;
			sel[r] = true;
			rest[r] = X;
			cifra[r] = 1;
		}
	}
	print(0);
	
	return 0;
}