Cod sursa(job #2799354)

Utilizator lucamLuca Mazilescu lucam Data 12 noiembrie 2021 23:47:15
Problema Multiplu Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <bits/stdc++.h>

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

/// Basic queue implementation, std::queue is too slow as, it is implemented as a linked list internally.
template<typename T, int N>
struct Queue {
    T m_data[N];
    int m_top = 0, m_bot = 0;
    T front() {
        return m_data[m_bot];
    }
    T pop() {
        return m_data[m_bot++];
    }
    void push(T val) {
        m_data[m_top++] = val;
    }
    bool empty() const {
        return m_top == m_bot;
    }
    void reset() {
        m_top = m_bot = 0;
    }
};

constexpr int N = 2e6;
bool vis[N];
int prev_mod[N];
int digit_count[N];
bool digit[N];
bool ans[N];
Queue<int, N> q;

/// Returns the greatest common divisor of a and b.
int gcd(int a, int b) {
	return b == 0 ? a : gcd(b, a % b);
}

void bfs(int mod) {
	q.push(1);
	vis[1] = true;
	prev_mod[1] = -1;
	digit[1] = 1;
	digit_count[1] = 1;

	bool found_0 = false;
	while (!(q.empty() || found_0)) {
		int m = q.pop();
		auto visit = [&](bool d) {
			int new_m = (m * 10 + d) % mod;
			if (vis[new_m]) {
				return;
			}

			q.push(new_m);
			vis[new_m] = true;
			prev_mod[new_m] = m;
			digit[new_m] = d;
			digit_count[new_m] = digit_count[m] + 1;

			found_0 = new_m == 0;
		};
		visit(0);
		visit(1);
	}
}

int main() {
	int a, b;
	in >> a >> b;
	int lcm = a / gcd(a, b) * b;
	bfs(lcm);
	int i = digit_count[0];
	for (int m = 0; m != -1; m = prev_mod[m]) {
		ans[--i] = digit[m];
	}
	for (int i = 0; i < digit_count[0]; ++i) {
		out << ans[i];
	}
	out << "\n";
}