Cod sursa(job #3148731)

Utilizator BuzdiBuzdugan Rares Andrei Buzdi Data 3 septembrie 2023 19:50:09
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <fstream>
#include <queue>
#include <string>

using namespace std;

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

const int NMAX = 2e6;
queue<int> Q;
pair<int, char> last[NMAX + 1];
bool viz[NMAX + 1];
char ans[NMAX + 3];

int gcd(int A, int B)
{
    while(B)
    {
        int R = A % B;
        A = B;
        B = R;
    }
    return A;
}

int main()
{
    int A, B;
    cin >> A >> B;

    int lcm = A * B / gcd(A, B);    
    
    Q.push(1);
    viz[1] = 1;
    last[1] = {-1, 1};

    // bool terminat = false;
    while(!Q.empty())
    {
        int rest = Q.front();
        Q.pop();

        int x = rest * 10;
        int y = x + 1;

        x %= lcm;
        y %= lcm;

        if(!viz[x])
        {
            Q.push(x);
            viz[x] = 1;
            last[x] = {rest, '0'};
        }
        if(!viz[y])
        {
            Q.push(y);
            viz[y] = 1;
            last[y] = {rest, '1'};            
        }
    }

    int rest = 0;
    int ind = 0;
    while(last[rest].first != -1)
    {
        ans[ind++] = last[rest].second;
        rest = last[rest].first;
    }
    ans[ind++] = '1';
    for(int i = ind - 1; i >= 0; i--)
        cout << ans[i];

    // cout << ans;
    
    return 0;
}