Cod sursa(job #2211162)

Utilizator felixiPuscasu Felix felixi Data 9 iunie 2018 14:29:44
Problema Multiplu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 2000000;

bool used[NMAX+2];
int pre[NMAX+2], tip[NMAX+2];
string sol;

int main()
{
    int A,B,M;
    in >> A >> B;
    if( A * B == 1 ) {
        out << "1\n";
        return 0;
    }
    M = A / __gcd(A,B) * B;
    queue<int> Q;
    Q.push(1);
    used[1] = 1;
    int gasit = 0;
    while( !Q.empty() && !gasit ) {  /// meh
        int nod = Q.front();
        Q.pop();
        for( int cif = 0;  cif < 2;  ++cif ) {
            int x = (nod * 10 + cif) % M;
            if( used[x] ) continue;

            if( x == 0 ) {
                sol.push_back('0' + cif);
                gasit = nod;
                break;
            }

            used[x] = 1;
            pre[x] = nod;
            tip[x] = cif;
            Q.push(x);
        }
    }
    gasit = pre[gasit];
    while( gasit ) {
        sol.push_back('0' + tip[gasit]);
        gasit = pre[gasit];
    }
    reverse(sol.begin(), sol.end());
    out << '1' << sol << '\n';
    return 0;
}