Pagini recente » Cod sursa (job #2337018) | Cod sursa (job #38817) | Cod sursa (job #2168044) | Cod sursa (job #2065191) | Cod sursa (job #2799354)
#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";
}