Cod sursa(job #2264137)

Utilizator flibiaVisanu Cristian flibia Data 19 octombrie 2018 20:27:08
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("multiplu.in");
ofstream out("multiplu.out");

int a, b, vf, tip[2000010], pv[2000010], md[2000010];
bitset <2000010> viz;
queue <int> q;

void rec(int p) {
	if (p == 0)
		return;
	rec(pv[p]);
	out << tip[p];
}

int main() {
	in >> a >> b;
	int mod = a * b / __gcd(a, b);
	viz[vf = 1] = 1;
	tip[vf] = 1;
	md[vf] = 1;
	q.push(1);
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		if (md[x] == 0) {
			rec(x);
			return 0;
		}
		for (int i = 0; i < 2; i++) {
			int aux = 10 * md[x] + i;
			aux %= mod;
			if (!viz[aux]) {
				viz[aux] = 1;
				tip[++vf] = i;
				md[vf] = aux;
				pv[vf] = x;
				q.push(vf);
			}
		}
	}
	return 0;
}