Cod sursa(job #3225828)

Utilizator edi482Eduard Vintu edi482 Data 19 aprilie 2024 09:50:33
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
bitset<2000002> fr;
string sol;
int q[2000002] , pred[2000002];
char c[2000002];
int main()
{
    int a , b , x , i;
    fin >> a >> b;
    x = a / __gcd(a , b) * b;
    int pr , ul;
    pr = ul = 1;
    q[pr] = 1;
    c[pr] = '1';
    fr[1] = 1;
    while (fr[0] == 0)
    {
        a = q[pr];
        pr++;
        b = a * 10 % x;
        if(fr[b] == 0)
        {
            fr[b] = 1;
            q[++ul] = b;
            c[ul] = '0';
            pred[ul] = pr - 1;
        }
        if(b == 0)
            break;
        b = (a * 10 + 1) % x;
        if(fr[b] == 0)
        {
            fr[b] = 1;
            q[++ul] = b;
            c[ul] = '1';
            pred[ul] = pr - 1;
        }
    }
    while(ul != 0)
    {
        sol += c[ul];
        ul = pred[ul];
    }
    reverse(sol.begin(),sol.end());
    fout << sol;
    return 0;
}