Cod sursa(job #1570891)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 16 ianuarie 2016 21:57:48
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <fstream>
#include <algorithm>
#include <queue>

using namespace std;

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

const int MAX_N = 2000000;

int P[1 + MAX_N];
queue < int > Q;

int gcd(int a, int b) {
    if(b == 0) {
        return a;
    }
    return gcd(b, a%b);
}

int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

void remakePath(int u) {
    if(u == 1) {
        out << 1;
        return;
    }
    else {
        remakePath(abs(P[u]));
        if(P[u] < 0) {
            out << 1;
        }
        else {
            out << 0;
        }
    }
}

int main() {
    int a, b, n, i, u, v;

    in >> a >> b;

    n = lcm(a, b);
    Q.push(1);

    while(!Q.empty()) {
        u = Q.front();
        Q.pop();

        if(u == 0) {
            break;
        }

        v = (u * 10) % n;
        if(P[v] == 0) {
            P[v] = u;
            Q.push(v);
        }
        v = (u * 10 + 1) % n;
        if(P[v] == 0) {
            P[v] = -u;
            Q.push(v);
        }
    }

    remakePath(0);
    return 0;
}