Cod sursa(job #2530301)

Utilizator Anastasia11Susciuc Anastasia Anastasia11 Data 24 ianuarie 2020 17:15:13
Problema Multiplu Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <queue>
#define ll long long
#define Nmax 2000005

using namespace std;

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

int a, b, m;
queue <long long> Q;
bool resturi[Nmax];

int main()
{
    f >> a >> b;
    m=a*b/__gcd(a, b);
    // cout << m << " ";

    if (a == 1 && b == 1)
    {
        g << "1";
        return 0;
    }

    Q.push(1);
    resturi[1]=1;

    while (!Q.empty())
    {
        ll x=Q.front();
        Q.pop();
        ll copie=x;
        x=x*10+0; x%=m;
        if (x == 0)
        {
            g << copie*10 << '\n';
            return 0;
        }
        if (resturi[x] == 0)
        {
            resturi[x]=1;
            Q.push(copie*10+0);
        }
        x=copie*10+1; x%=m;
        if (x == 0)
        {
            g << copie*10+1 << '\n';
            return 0;
        }
        if (resturi[x] == 0)
        {
            resturi[x]=1;
            Q.push(copie*10+1);
        }
    }

    return 0;
}