Cod sursa(job #2262462)

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

const int MAX = 1005;

int a, b;
int lcm;
int zece[MAX];
map <int, pair <int, int> > da[MAX];
vector <int> rez;

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

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

int main()
{
    fi >> a >> b;
    lcm = a * b / gcd(a, b);


    precalc();

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

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

    cout << da[3][0].second;

    while (acolo != -1)
    {
        rez.push_back(acolo);
        acolo = da[acolo][0].second;
    }

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

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

    return 0;
}