Pagini recente » Cod sursa (job #947532) | Cod sursa (job #120775) | Cod sursa (job #1338568) | Cod sursa (job #2021177) | Cod sursa (job #2263197)
#include <bits/stdc++.h>
#define pb push_back
#define int long long
using namespace std;
ifstream fi("multiplu.in");
ofstream fo("multiplu.out");
int a, b, lcm;
int curr;
vector <int> cif, ult, rez;
map <int, bool> avem;
queue < pair <int, int> > Q; /// (restul, momentul)
int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
signed main()
{
fi >> a >> b;
lcm = a * b / gcd(a, b);
Q.push({1, 0});
avem[1] = 0;
ult.pb(-1);
cif.pb(1);
int deacolo = -1;
while (!Q.empty())
{
pair <int, int> nod = Q.front();
Q.pop();
int r = nod.first, t = nod.second;
avem[r] = 0;
if (r == 0)
{
deacolo = t;
break;
}
/// bagam 0 la final
if (!avem[r * 10 % lcm])
{
curr++;
Q.push({r * 10 % lcm, curr});
avem[r * 10 % lcm] = 1;
ult.pb(t);
cif.pb(0);
}
/// bagam 1
if (!avem[(r * 10 + 1) % lcm])
{
curr++;
Q.push({(r * 10 + 1) % lcm, curr});
avem[(r * 10 + 1) % lcm] = 1;
ult.pb(t);
cif.pb(1);
}
}
while (deacolo != -1)
{
rez.pb(cif[deacolo]);
deacolo = ult[deacolo];
}
reverse(rez.begin(), rez.end());
for (auto x: rez)
fo << x;
return 0;
}