Cod sursa(job #3218929)

Utilizator Alexbora13Bora Ioan Alexandru Alexbora13 Data 28 martie 2024 16:46:41
Problema Multiplu Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <bitset>
#include <algorithm>

using namespace std;

const int MAX = 2000000;

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

bitset<MAX + 1> bifat, cif;
int pre[MAX + 1];

void reconstruct(int x) {
    if (pre[x]!=0) reconstruct(pre[x]);
    fout << cif[x];
}

int main() {
    int A, B;
    fin >> A >> B;

    queue<int> Q;
    Q.push(1);
    cif[1] = 1;
    bifat[1] = 1;
    int cmmmc = A / __gcd(A, B) * B;

    while (!Q.empty()) {
        int val = Q.front();
        if (val == 0) {
            reconstruct(val);
            break;
        }
        Q.pop();
        if (val * 10 <= MAX && !bifat[(val * 10)%cmmmc]) {
            bifat[(val * 10)%cmmmc] = 1;
            cif[(val * 10)%cmmmc] = 0;
            pre[(val * 10)%cmmmc] = val;
            Q.push((val * 10)%cmmmc);
        }
        if (val * 10 + 1 <= MAX && !bifat[(val * 10 + 1)%cmmmc]) {
            bifat[(val * 10 + 1)%cmmmc] = 1;
            cif[(val * 10 + 1)%cmmmc] = 1;
            pre[(val * 10 + 1)%cmmmc] = val;
            Q.push((val * 10 + 1)%cmmmc);
        }
    }
    return 0;
}