Cod sursa(job #2262964)

Utilizator CammieCamelia Lazar Cammie Data 17 octombrie 2018 22:49:17
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <fstream>
#include <queue>
#include <bitset>

#define MAXN 2000004

using namespace std;

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

inline int cmmdc(int a, int b) {
    int r;
    do {
        r = a % b;
        a = b;
        b = r;
    } while (r);

    return a;
}

bitset <MAXN> val, fr;
queue <int> Q;
int pred[MAXN];

void Afis(int poz) {
    if (pred[poz]) {
        Afis(pred[poz]);
        fout << val[poz];
    }
    else
        fout << poz;
}

int multiplu;

inline void Solve() {
    Q.push(1); pred[1] = 0; val[1] = 1; fr[1] = 1;

    int x, val1, val2, modulo;

    while (!Q.empty()) {
        x = Q.front();

        val1 = x * 10 + 0;
        if (val1 % multiplu == 0) {
            val[0] = 0; pred[0] = x;
            Afis(0);
            return;
        }
        else {
            modulo = val1 % multiplu;
            if (!fr[modulo]) {
                fr[modulo] = 1;
                pred[modulo] = x; val[modulo] = 0;
                Q.push(modulo);
            }
        }

        val2 = x * 10 + 1;
        if (val2 % multiplu == 0) {
            val[0] = 1; pred[0] = x;
            Afis(0);
            return;
        }
        else {
            modulo = val2 % multiplu;
            if (!fr[modulo]) {
                fr[modulo] = 1;
                val[modulo] = 1; pred[modulo] = x;
                Q.push(modulo);
            }
        }

        Q.pop();
    }
}

inline void Read() {
    int A, B, div;

    fin >> A >> B;

    div = cmmdc(A, B);
    multiplu = (1LL * A * B) / div;
}

int main () {
    Read();
    Solve();

    fin.close(); fout.close(); return 0;
}