Cod sursa(job #2264145)

Utilizator netfreeAndrei Muntean netfree Data 19 octombrie 2018 20:32:42
Problema Multiplu Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <bits/stdc++.h>
#define var long long

using namespace std;

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

const var N_MAX = 10000000 + 5;

var a, b, M;
var cif[N_MAX], up[N_MAX];
bitset<N_MAX> inq;
queue<var> q;

void show(var x){
    if(up[x]){
        show(up[x]);
        fout << cif[x];
    } else
        fout << 1;

    return;
}

void solve(){
    q.push(1); inq[1] = 1;
    cif[1] = 1; up[1] = 0;

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

        if(x == 0){
            show(0);
            //cout << "IN GOD WE TRUST";
            return;
        }

        var mod1 = (x*10)%M;
        if(!inq[mod1]){
            inq[mod1] = true;
            q.push(mod1);
            up[mod1] = x;
            cif[mod1] = 0;
        }

        var mod2 = (x*10+1)%M;
        if(!inq[mod2]){
            inq[mod2] = true;
            q.push(mod2);
            up[mod2] = x;
            cif[mod2] = 1;
        }
    }
}

int main()
{
    fin >> a >> b;
    M = (a*b)/__gcd(a,b);
    solve();
    return 0;
}