Pagini recente » Cod sursa (job #1582915) | Cod sursa (job #87682) | Cod sursa (job #2203877) | Cod sursa (job #804272) | Cod sursa (job #2268441)
#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;
}