Cod sursa(job #2120223)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 2 februarie 2018 10:08:15
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <fstream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

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

const int nmax = 2e6;
const int inf = 1 << 30;

int t[nmax + 1], c[nmax + 1];
bool viz[nmax + 1];

queue< int > q;
vector< int > v;

int gcd (int a, int b) {
    while (b > 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int main () {
    int a, b;
    fin >> a >> b;

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

    q.push( 1 );
    t[ 1 ] = 0;
    viz[ 1 ] = 1;

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

        for (int cif = 0; cif < 2; ++ cif) {
            int y = (x * 10 + cif) % lcm;

            if (viz[ y ] == 0) {
                t[ y ] = x;
                c[ y ] = cif;

                viz[ y ] = 1;
                q.push( y );
            }
        }
    }

    int r = 0;
    while (r != 1) {
        v.push_back(c[ r ]);
        r = t[ r ];
    }

    v.push_back( 1 );
    reverse(v.begin(), v.end());

    for (auto i : v) {
        fout.put(i + '0');
    }

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