Cod sursa(job #2840912)

Utilizator TudosieRazvanTudosie Marius-Razvan TudosieRazvan Data 28 ianuarie 2022 23:36:01
Problema Multiplu Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <fstream>
#include <queue>
#include <vector>
#define NMAX 6000005
using namespace std;

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

bool viz[NMAX];
int cif[NMAX], tata[NMAX];
const int val[2] = { 1,0 };

void reinit()
{
    for (int i = 1; i <= NMAX; i++)
    {
        tata[i] = -1;
        cif[i] = 0;
    }
}

void cautNumar(int rest, int imp)
{
    reinit();
    queue<int> q;
    q.push(1);
    int sol = -1;
    while (!q.empty())
    {
        int elem = q.front();
        q.pop();
        for (int i = 0; i < 2; i++)
        {
            int num = elem * 10 + val[i];
            num %= imp;
            if (!viz[num])
            {
                viz[num] = true;
                q.push(num);
                cif[num] = val[i];
                tata[num] = elem;

                if (num == rest)
                {
                    sol = num;
                    break;
                }
            }
        }
    }
    if (sol == -1)
    {
        //nu am solutie
        fout << "-1\n";
        return;
    }
    //parcurg vec de tati
    vector<int>s;
    s.push_back(cif[sol]);
    while (tata[sol] > 0)
    {
        sol = tata[sol];
        s.push_back(cif[sol]);
    }
    for (int i = s.size() - 1; i >= 0; i--)
    {
        fout << s[i];
    }
    fout << "\n";
}

int cmmdc(int a, int b)
{
    int rest = a % b;
    while (rest != 0)
    {
        a = b;
        b = rest;
        rest = a % b;
    }
    return b;
}

int main()
{
    int a, b;
    fin >> a >> b;
    int cmdc = cmmdc(a, b);
    int cmmmc = (a / cmdc) * (b / cmdc);
    cautNumar(0, cmmmc);
    return 0;
}