Cod sursa(job #2794493)

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

using namespace std;

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

int a, b;

pair <int, int> per[2000002]; ///ant w/ pAct
int stk[2000002];
int vf = 0;
int lll = 0;
int main()
{
    in >> a >> b;
    int mod = a * b / __gcd(a, b);
    int put10 = 1;
    int cnr = 0;
    while(true){
        for(int i = vf - 1; i >= 0; i--){
            int x = stk[i];
            lll++;
            if(per[(put10 + x) % mod].first == 0)
                stk[vf++] = (put10 + x) % mod, per[(put10 + x) % mod].first = x, per[(put10 + x) % mod].second = cnr;
        }
        if(per[put10].first == 0)
            stk[vf++] = put10, per[put10].first = -1, per[put10].second = cnr;
        if(per[0].first != 0)
            break;
        put10 *= 10, put10 %= mod, cnr++;
    }
    string s(cnr + 1, '0');
    int x = 0;
    while(x != -1){
        s[per[x].second] = '1';
        x = per[x].first;
    }
    reverse(s.begin(), s.end());
    out << s << "\n";

    return 0;
}