Cod sursa(job #2913383)

Utilizator AlexDavid26Alex Bleotu AlexDavid26 Data 14 iulie 2022 10:03:08
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

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

const int XMAX = 2000005;

int prv[XMAX], x;

queue<int> numbersQueue;

int cmmdc(int a, int b) {
	int r = a % b;
	while (r)
		a = b, b = r, r = a % b;
	return b;
}

void reconst(int r) {
	if (r == 1) {
		fout << "1";
		return;
	}
	int rest = prv[r];

	reconst(rest);
	if ((rest * 10) % x == r)
		fout << "0";
	else
		fout << "1";
}

int main() {
	int a, b;
	fin >> a >> b;

	x = a * b / cmmdc(a, b);
	for (int i = 0; i < x; i++)
		prv[i] = -1;

	prv[1] = 1;
	numbersQueue.push(1);
	while (!numbersQueue.empty()) {
		int r = numbersQueue.front();
		numbersQueue.pop();

		if (!r)
			break;
		int r0 = (r * 10) % x;
		if (prv[r0] == -1) {
			prv[r0] = r;
			numbersQueue.push(r0);
		}
		int r1 = (r * 10 + 1) % x;
		if (prv[r1] == -1) {
			prv[r1] = r;
			numbersQueue.push(r1);
		}
	}
	reconst(0);
}