Cod sursa(job #2768457)

Utilizator DragosC1Dragos DragosC1 Data 10 august 2021 19:37:04
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <fstream>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int a, b, m;

void read() {
    ifstream f("multiplu.in");
    f >> a >> b;
    f.close();
}

int cmmmc(int a, int b) {
    int ca = a, cb = b, r;
    while (b) {
        r = a % b;
        a = b;
        b = r;
    }
    return ca * cb / a;
}

int poz[2000001];
bool digit[2000001];

queue<int> Q;
vector<int> v;
void solve() {
    int i, x;
    m = cmmmc(a, b);
    Q.push(1);
    poz[1] = -1;
    digit[1] = 1;
    while (!Q.empty()) {
        x = Q.front();
        Q.pop();
        if (x == 0)
            break;
        if (poz[(x * 10) % m] == 0) {
            poz[(x * 10) % m] = x;
            digit[(x * 10) % m] = 0;
            Q.push((x * 10) % m);
        } 
        if (poz[(x * 10 + 1) % m] == 0) {
            poz[(x * 10 + 1) % m] = x;
            digit[(x * 10 + 1) % m] = 1;
            Q.push((x * 10 + 1) % m);
        } 
    }
    x = 0;
    while (x != -1) {
        v.emplace_back(digit[x]);
        x = poz[x];
    }
}

void output() {
    int i;
    ofstream g("multiplu.out");
    for (i = v.size() - 1; i >= 0; i--)
        g << v[i];
    g.close();
}

int main() {
    read();
    solve();
    output();
    return 0;
}