Cod sursa(job #3361258)

Utilizator EricDimiCismaru Eric-Dimitrie EricDimi Data 22 iulie 2026 14:35:03
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <fstream>
#include <queue>

using namespace std;

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

const int MAX_M = 2000000;

int up[MAX_M],
    dig[MAX_M];
int M, A, B;

int gcd(int x, int y)
{
    int r;
    while(y != 0)
    {
        r = x % y;
        x = y;
        y = r;
    }
    return x;
}

inline int lcm(int x, int y)
{
    return x / gcd(x, y) * y;
}

void Read()
{
    f >> A >> B;
    M = lcm(A, B);
}

void Init()
{
    for(int i = 0; i < M; i++)
        dig[i] = -1;
}

void BFS()
{
    queue<int> Q;

    up[1] = -1;
    dig[1] = 1;
    Q.push(1);

    while(!Q.empty())
    {
        int rem = Q.front();
        Q.pop();

        if(!rem)
            return;

        for(int d : {0, 1})
        {
            int val = (rem * 10 + d) % M;
            if(dig[val] == -1)
            {
                up[val] = rem;
                dig[val] = d;
                Q.push(val);
            }
        }
    }
}

void PrintAns(int rem)
{
    if(up[rem] == -1)
        g << dig[rem];
    else
    {
        PrintAns(up[rem]);
        g << dig[rem];
    }
}

int main()
{
    Read();
    Init();
    BFS();
    PrintAns(0);

    f.close();
    g.close();

    return 0;
}