Cod sursa(job #2262793)

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

const ll MAX = 105;

ll a, b;
ll lcm;
ll zece[MAX];
unordered_map <ll, pair <ll, ll> > da[MAX];
vector <ll> rez;

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

void precalc()
{
    zece[0] = 1;
    for (ll i = 1; i < MAX; i++)
        zece[i] = zece[i - 1] * 10 % lcm;
}

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

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

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

    precalc();

    ll acolo = -1;
    for (ll i = 0; i < MAX; i++)
    {
        da[i][zece[i]] = {1, -1};
        if (zece[i] == 0)
            acolo = i;
        if (acolo != -1)
            break;

        for (ll j = 0; j < i; j++)
        {
            for (auto x: da[j])
            {
                if (da[i][(x.first + zece[i]) % lcm].first != 1)
                   da[i][(x.first + zece[i]) % lcm] = {1, j};
                if ((x.first + zece[i]) % lcm == 0)
                {
                    acolo = i;
                    break;
                }
            }
        }
    }

    ll vrem = 0;
    while (acolo != -1)
    {
        rez.push_back(acolo);

        ll auxAcolo = acolo;
        acolo = da[acolo][vrem].second;

        vrem = vrem - zece[auxAcolo];

        while (vrem < 0)
           vrem += lcm;
        //cout << vrem << " ";
    }

   // for (auto x: rez)
       //cout << x << " ";
   // return 0;

    ll dist = 0, ult = rez.front();
    for (auto x: rez)
    {
        dist = ult - x;
        for (ll i = 1; i < dist; i++)
            fo << 0;
        fo << 1;
        ult = x;
    }

    for (ll i = 1; i <= ult; i++)
        fo << 0;

    return 0;
}