Cod sursa(job #2276243)

Utilizator TooHappyMarchitan Teodor TooHappy Data 4 noiembrie 2018 14:24:29
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <bits/stdc++.h>
using namespace std;
 
ifstream in("multiplu.in");
ofstream out("multiplu.out");

const int Nmax = 2e6 + 10;

int gcd(int a, int b) {
    return (b ? gcd(b, a % b) : a);
}

int tata[Nmax], cif[Nmax];
queue< int > q;

void getNumber(int x) {
    if(x == -1) {
        return;
    }
    getNumber(tata[x]);

    out << cif[x];
}

int main() {
    ios::sync_with_stdio(false); in.tie(0); out.tie(0);

    int a, b; in >> a >> b;

    int m = (a * b) / gcd(a, b);

    if(m == 1) {
        out << "1\n";
        return 0;
    }

    q.push(1);
    tata[1] = -1;
    cif[1] = 1;

    while(!q.empty()) {
        int x = q.front(); q.pop();

        for(int i = 0; i < 2; ++i) {
            int nx = 10 * x + i;
            int r = nx % m;

            if(tata[r]) {
                continue;
            }

            q.push(r);
            tata[r] = x;
            cif[r] = i;

            if(r == 0) {
                getNumber(0);
                return 0;
            }
        }
    }

    in.close(); out.close();

    return 0;
}