Cod sursa(job #2268441)

Utilizator DavidLDavid Lauran DavidL Data 24 octombrie 2018 20:16:22
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
using namespace std;
ifstream fi("multiplu.in");
ofstream fo("multiplu.out");

const int MAX = 2000005;

ll a, b, lcm;
ll curr;
vector <ll> rez;
int cif[MAX], ult[MAX];
bool avem[MAX];
queue < pair <ll, ll> > Q; /// (restul, momentul)

ll modCalc(ll a, ll b)
{
   while (a >= b)
      a -= b;
   return a;
}

ll gcd(ll a, ll b)
{
    if (b == 0)
        return a;
    return gcd(b, modCalc(a, b));
}

signed main()
{
    fi >> a >> b;

    if (a + b == 1)
    {
        fo << 1;
        return 0;
    }

    lcm = a * b / gcd(a, b);

    Q.push({1, 0});
    avem[1] = 0;
    ult[curr] = -1;
    cif[curr] = 1;

    ll deacolo = -1;

    ll it = 0;
    while (!Q.empty())
    {
        it++;

        pair <ll, ll> nod = Q.front();
        Q.pop();

        ll r = nod.first, t = nod.second;

        /// bagam 0 la final
        if (!avem[modCalc(r * 10, lcm)])
        {
            curr++;
            Q.push({modCalc(r * 10, lcm), curr});
            avem[modCalc(r * 10, lcm)] = 1;
            ult[curr] = t;
            cif[curr] = 0;

            if (modCalc(r * 10, lcm) == 0)
            {
               deacolo = curr;
               break;
            }
        }

        /// bagam 1
        if (!avem[modCalc(r * 10 + 1, lcm)])
        {
            curr++;
            Q.push({modCalc(r * 10 + 1, lcm), curr});
            avem[modCalc(r * 10 + 1, lcm)] = 1;
            ult[curr] = t;
            cif[curr] = 1;

            if (modCalc(r * 10 + 1, lcm) == 0)
            {
               deacolo = curr;
               break;
            }
        }
    }

    //cout << it;
    //return 0;


    while (deacolo != -1)
    {
        rez.pb(cif[deacolo]);
        deacolo = ult[deacolo];
    }

    reverse(rez.begin(), rez.end());
    for (auto x: rez)
        fo << x;

    return 0;
}