Cod sursa(job #2964653)

Utilizator IvanAndreiIvan Andrei IvanAndrei Data 13 ianuarie 2023 16:06:19
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <fstream>
#include <queue>
#include <algorithm>
#include <vector>

using namespace std;

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

const int max_size = 2e6 + 1;

int viz[max_size], t[max_size], sol[max_size], x, ans;
queue <int> q;
vector <int> rez;

void bfs ()
{
    q.push(1);
    viz[1] = 1;
    sol[1] = 1;
    while (!q.empty())
    {
        int nod = q.front();
        q.pop();
        for (int i = 0; i < 2; i++)
        {
            int nou = (nod * 10 + i) % x;
            if (viz[nou] == 0)
            {
                viz[nou] = 1;
                sol[nou] = i;
                t[nou] = nod;
                if (nou == 0)
                {
                    ans = nou;
                    break;
                }
                q.push(nou);
            }
        }
    }
}

int main ()
{
    int a, b;
    in >> a >> b;
    x = a * b / __gcd(a, b);
    bfs();
    int ind = 0;
    while (ind != 1)
    {
        rez.push_back(sol[ind]);
        ind = t[ind];
    }
    reverse(rez.begin(), rez.end());
    out << 1;
    for (auto f : rez)
    {
        out << f;
    }
    in.close();
    out.close();
    return 0;
}