Cod sursa(job #1540255)

Utilizator tudorcomanTudor Coman tudorcoman Data 2 decembrie 2015 15:39:50
Problema Multiplu Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb

#include <cstdio>
#include <deque>
using namespace std;

const int maxN = 2e6;

class Nod {
public:
	int cif, tata, rest;
	Nod(int _cif = 0, int _tata = 0, int _rest = 0) : 
		cif(_cif), tata(_tata), rest(_rest) { }
};

Nod C[maxN + 1];
int first, last;
int f[maxN + 1];

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

deque<int> sol;

int main() {
	freopen("multiplu.in", "r", stdin);
	freopen("multiplu.out", "w", stdout);
	int A, B;
	scanf("%d %d", &A, &B);
	int prod = A * B;
	if(prod == 1) {
		puts("1");
		return 0;
	}	
	int lcm = prod / gcd(A, B);
	C[++ last] = Nod(1, -1, 1);
	first = 1;
	while(first <= last) {
		int val = C[first].rest;
		if(!f[(val * 10) % lcm]) {
			C[++ last] = Nod(0, first, (val * 10) % lcm);
			if((val * 10) % lcm == 0)
				break;
			++ f[(val * 10) % lcm];
		}
		if(!f[(val * 10 + 1) % lcm]) {
			C[++ last] = Nod(1, first, (val * 10 + 1) % lcm);
			if((val * 10 + 1) % lcm == 0)
				break;
			++ f[(val * 10) + 1 % lcm];
		}
		++ first;
	}

	Nod x = C[last];
	while(x.tata != -1) {
		sol.push_front(x.cif);
		x = C[x.tata];
	}

	sol.push_front(1);
	for(auto it = sol.begin(); it != sol.end(); ++ it)
		printf("%d", *it);
	printf("\n");
	return 0;
}