Pagini recente » Cod sursa (job #2682203) | Cod sursa (job #868346) | Cod sursa (job #2298986) | Cod sursa (job #1323987) | Cod sursa (job #2262793)
#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;
}