Cod sursa(job #2866374)

Utilizator vladutzu_finutzuVlad Cacenschi vladutzu_finutzu Data 9 martie 2022 17:37:31
Problema Multiplu Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <fstream>
#include <queue>
using namespace std;
ifstream cin("multiplu.in");
ofstream cout("multiplu.out");
int a, b;
queue <int> Q;
pair<int, int> ant[2000005];
int getCMMMC(int x, int y)
{
    int r = x % y, p = x * y;
    while(r)
    {
        x = y;
        y = r;
        r = x % y;
    }
 
    return p / y;
}
void traceback(int r)
{
    if(r == 1)
    {
        cout<<'1';
        return;
    }
    
    traceback(ant[r].first);
    cout << ant[r].second;
}
int main()
{
    cin>>a>>b;
 
    int m = getCMMMC(a, b);
 
    if(1 % m == 0)
    {
        cout<<1;
        return 0;
    }
 
    Q.push(1);
 
    while(!Q.empty())
    {
        int r = Q.front();
        Q.pop();
 
        for(int i=0; i<=1; i++)
        {
            int nr = (1LL * r * 10 + i) % m;
            if(ant[nr].first == 0)
                ant[nr] = {r, i}, Q.push(nr);
            
            if(nr == 0)
            {
                traceback(nr);
                return 0;
            }
        }
    }
 
    return 0;
}