Cod sursa(job #2794503)

Utilizator stefan.popescuPopescu Stefan stefan.popescu Data 4 noiembrie 2021 23:49:50
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <bits/stdc++.h>

using namespace std;

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

int a, b;

pair <int, bool> per[2000002]; ///ant w/ pAct
int q[2000002];

int ll, rr;

string s;

void getAns(int act){
    if(act == -1)
        return;
    getAns(per[act].first);
    s.push_back('0' + per[act].second);
}

int main()
{
    in >> a >> b;
    int mod = a * b / __gcd(a, b);
    ll = 0, rr = 1;
    q[0] = 1;
    per[1] = {-1, true};
    while(ll < rr){
        int nxt = (q[ll] * 10) % mod;
        if(per[ nxt ].first == 0){
            q[rr++] = nxt;
            per[nxt] = {q[ll], false};
            if(nxt == 0)
                break;
        }
        nxt = (q[ll] * 10 + 1) % mod;
        if(per[ nxt ].first == 0){
            q[rr++] = nxt;
            per[nxt] = {q[ll], true};
            if(nxt == 0)
                break;
        }
        ll++;
    }
    getAns(0);

    out << s << "\n";

    return 0;
}