Cod sursa(job #2913382)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 14 iulie 2022 10:01:26
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <fstream>
#include <queue>

using namespace std;

ofstream fout("multiplu.out");
const int Xmax = 2000005;

queue<int> Q;

int CMMDC(int a, int b) {
    int r = a % b;
    while(r) {
        a = b; b = r; r = a % b;
    }
    return b;
}

int prv[Xmax], X;

void reconst(int r) {
    if(r == 1) {
        fout <<'1';
        return;
    }
    int rest = prv[r];

    reconst(rest);
    if((rest * 10) % X == r) {
        fout << '0';
    }
    else {
        fout << '1';
    }
}

int main() {
    int A, B;
    ifstream fin("multiplu.in");
    fin >> A >> B;
    X = A * B / CMMDC(A, B);
    for(int i = 0; i < X; i++) {
        prv[i] = -1;
    }
    prv[1] = 1;
    Q.push(1);
    while(!Q.empty()) {
        int r = Q.front();
        Q.pop();
        if(!r) {
            break;
        }
        int r0 = (r * 10) % X;
        if(prv[r0] == -1) {
            prv[r0] = r;
            Q.push(r0);
        }
        int r1 = (r * 10 + 1) % X;
        if(prv[r1] == -1) {
            prv[r1] = r;
            Q.push(r1);
        }
    }
    reconst(0);
    return 0;
}