Cod sursa(job #2785114)

Utilizator lucamLuca Mazilescu lucam Data 17 octombrie 2021 23:46:09
Problema Multiplu Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.61 kb
#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';
}