Cod sursa(job #3166528)

Utilizator juniorOvidiu Rosca junior Data 8 noiembrie 2023 21:48:51
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <fstream>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int cmmdc(int d, int i) {
    int r;

    do {
        r = d % i;
        d = i;
        i = r;
    } while (r != 0);
    return d;
}

int cmmmmc(int a, int b) { return (a * b) / cmmdc(a, b); }

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

    int A, B;
    fin >> A >> B;

    int M = cmmmmc(A, B);           // Calculam cel mai mic multiplu comun pentru A si B
    vector<bool> obtinut(M, false); // Vector pentru a verifica daca un rest a fost vizitat sau nu
    vector<int> p(M);               // restul precedent
    vector<int> cifra(M);           // cifra corespunzatoare unui anumit rest

    queue<int> q;
    q.push(1); // Introducem restul numarului 1 la impartirea cu M
    obtinut[1] = true;
    p[1] = -1; // Inaintea primului rest nu avem o alt rest.
    cifra[1] = 1;

    while (not q.empty()) {
        int c = q.front(); // restul curent
        q.pop();
        if (c == 0) { // Daca restul este 0, am gasit numarul
            vector<int> sol;
            for (int i = 0; c != -1; c = p[c]) {
                sol.push_back(cifra[c]);
            }
            for (int i = sol.size() - 1; i >= 0; --i) {
                fout << sol[i];
            }
            fout << '\n';
            break;
        }
        for (int i : {0, 1}) {
            int urm = (c * 10 + i) % M; // Adaugam cifra 0 la sfarsitul
            if (not obtinut[urm]) {
                q.push(urm);
                obtinut[urm] = true;
                p[urm] = c;
                cifra[urm] = i;
            }
        }
    }
    fin.close();
    fout.close();
    return 0;
}