Cod sursa(job #3278382)

Utilizator ShAwDoRneYNacu Gabriel ShAwDoRneY Data 19 februarie 2025 17:06:42
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const int M = 2e6;

int cmmdc(int A, int B) {

    while(B != 0) {
        int r = A % B;
        A = B;
        B = r;
    }
    return A;
}

int cmmmc(int A, int B) {

    return A * B / cmmdc(A,B);
}

void refac_numarul(int x, vector<pair<int,int> > &previous) {

    if(x == 1) {
        fout << 1;
        return ;
    }
    
    refac_numarul(previous[x].first, previous);

    fout << previous[x].second;
}

int main() {

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

    int m = cmmmc(A,B);

    vector<pair<int,int>> previous(m, {-1, -1});
    queue<int> Q;
    Q.push(1);
    previous[1].first = 0;
    previous[1].second = -1;

    while(!Q.empty()) {

        int x = Q.front();
        Q.pop();

        int y = x*10 % m;
        
        if(previous[y].first == -1) {
            previous[y].first = x;
            previous[y].second = 0;
            Q.push(y);
        }

        int z = (x*10+1) % m;

        if(previous[z].first == -1) {
            previous[z].first = x;
            previous[z].second = 1;
            Q.push(z);
        }
    }

    refac_numarul(0, previous);

    return 0;
}