Cod sursa(job #1929431)

Utilizator eu3neuomManghiuc Teodor-Florin eu3neuom Data 17 martie 2017 17:10:19
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMax = 2e6 + 5;

int up[NMax];
int ans[NMax];
bool value[NMax];
bool viz[NMax];

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

    return a;
}

int main() {
    ios::sync_with_stdio(false);

    int a, b;
    fin >> a >> b;

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

    deque < int > dq;
    dq.push_back(1);
    viz[1] = true;

    while(viz[0] == false) {
        int x = dq.front(); dq.pop_front();

        for(int i = 0; i <= 1; i++) {
            int aux = (x * 10 + i) % m;

            if(viz[aux] == false) {
                up[aux] = x;
                value[aux] = i;

                dq.push_back(aux);
                viz[aux] = true;
            }
        }
    }

    int next = 0;
    while(up[next] != 0) {
        ans[++ans[0]] = value[next];
        next = up[next];
    }

    ans[++ans[0]] = 1;
    for(int i = ans[0]; i > 0; i--) fout << ans[i];

    return 0;
}