Cod sursa(job #3225835)

Utilizator DenisBadarauDenisBadarau DenisBadarau Data 19 aprilie 2024 09:51:49
Problema Multiplu Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("in.in");
ofstream fout("out.out");

int q[2000001] ,pr , ul;
int pred[2000000];
char c[2000003];
bitset<2000001> fr;
string sol;

int main()
{
    int x , a , b , i;
    fin >> a >> b;
    x = a / __gcd(a,b) * b;
    pr = ul = 1;
    q[pr] = 1;
    fr[1] = 1;
    c[pr] = '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;
}