Cod sursa(job #3278383)

Utilizator CiorpionanRoman Matei-Ciprian Ciorpionan Data 19 februarie 2025 17:07:19
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

const int M = 2e6;

int cmmmc(int a, int b){
    int n = a, m = b;
    while (m != n){
        if (n < m){
            n += a;
        }
        else if(n > m){
            m += b;
        }
    }
    return n;
}

void refac_numarul(int x, vector<pair<int, int>> &pred, ofstream &out){
    if (x == 1){
        out << 1;
        return;
    }
    refac_numarul(pred[x].first, pred, out);
    out << pred[x].second;
}

int main()
{
    ifstream in("multiplu.in");
    ofstream out("multiplu.out");
    int a, b;
    in >> a >> b;
    int m = cmmmc(a, b);
    vector<bool> viz(m, false);
    pair <int, int> init = {-1, -1};
    vector<pair<int,int>> pred(m, init);
    queue<int> q;
    q.push(1);
    pred[1].first = 0;
    pred[1].second = -1;
    while (!q.empty()){
        int x = q.front();
        q.pop();
        int y = x * 10 % m;
        if (pred[y].first == -1){
            q.push(y);
            pred[y].first = x;
            pred[y].second = 0;
        }
        y = (x*10 + 1) % m;
        if (pred[y].first == -1){
            q.push(y);
            pred[y].first = x;
            pred[y].second = 1;
        }
    }
    refac_numarul(0, pred, out);
    in.close();
    out.close();
    return 0;
}