Pagini recente » Rezultatele filtrării | Borderou de evaluare (job #1529950) | Rezultatele filtrării | Cod sursa (job #2785114)
#include <bits/stdc++.h>
#ifdef ONLINE_JUDGE
#define in std::cin
#define out std::cout
#else
std::ifstream in("multiplu.in");
std::ofstream out("multiplu.out");
#endif
template<typename T, size_t N>
constexpr size_t length_of(T (&)[N]) { return N; }
constexpr int N = 2e6 + 1;
int dp[N];
int prev[N];
bool digit[N];
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;
}
};
void bfs(int mod) {
static Queue<int, N> q;
q.push(1);
dp[1] = 1;
prev[1] = -1;
digit[1] = 1;
bool found = false;
while (!(q.empty() || found)) {
int u = q.pop();
auto visit = [&](bool dig) {
int v = (u * 10 + dig) % mod;
if (dp[v] != 0 && dp[v] <= dp[u] + 1) return;
dp[v] = dp[u] + 1;
q.push(v);
prev[v] = u;
digit[v] = dig;
found = v == 0;
};
visit(0);
visit(1);
}
}
int main() {
int a, b;
in >> a >> b;
int lcm = a * b / std::__gcd(a, b);
bfs(lcm);
std::vector<int> number;
number.reserve(dp[0]);
for (int i = 0; i != -1; i = prev[i]) {
number.push_back(digit[i]);
}
for (auto it = number.rbegin(); it != number.rend(); ++it) {
out << *it;
}
out << '\n';
}