Cod sursa(job #3270876)

Utilizator unomMirel Costel unom Data 24 ianuarie 2025 19:10:38
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <fstream>
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

ifstream in("multiplu.in");
ofstream out("multiplu.out");
int a, b, c;
int d[2000005];
pair<int, int> op[2000005];
queue<int> q;
vector<int> rez;

int main()
{
    in>>a>>b;

    c = (a * b) / __gcd(a, b);

    d[1] = 1;
    q.push(1);

    while(!q.empty())
    {
        int i = q.front();
        q.pop();

        //cout<<i<<'\n';

        if(d[(i * 10) % c] == 0)
        {
            d[(i * 10) % c] = d[i] + 1;
            op[(i * 10) % c] = {0, i};

            q.push((i * 10) % c);
        }

        if(d[(i * 10 + 1) % c] == 0)
        {
            d[(i * 10 + 1) % c] = d[i] + 1;
            op[(i * 10 + 1) % c] = {1, i};

            q.push((i * 10 + 1) % c);
        }
    }

    int poz = 0;
    while(poz != 1)
    {
        //cout<<poz<<'\n';
        rez.push_back(op[poz].first);
        poz = op[poz].second;
    }
    rez.push_back(1);

    reverse(rez.begin(), rez.end());

    for(auto it: rez)
    {
        out<<it;
    }

    return 0;
}