Pagini recente » Cod sursa (job #989171) | Cod sursa (job #1122889) | Cod sursa (job #2637783) | Cod sursa (job #1214527) | Cod sursa (job #2429277)
// Datorez puntajul de la aceasta problema lui Bogdan Pop care mi-a spus solutia
// incercand sa-mi explice alta problema de fapt
#include <bits/stdc++.h>
#define DEBUG(x) cerr << (#x) << ": " << (x) << '\n'
using namespace std;
int main() {
freopen("multiplu.in", "r", stdin);
freopen("multiplu.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
int a, b;
cin >> a >> b;
int lcm = a * b / __gcd(a, b);
vector<int> dad(lcm), digit(lcm);
digit[1] = 1;
dad[1] = -1;
queue<int> q;
q.push(1);
while (!q.empty()) {
int node = q.front();
q.pop();
if (node == 0) {
break;
}
for (int dig : {0, 1}) {
int to = (node * 10 + dig) % lcm;
if (dad[to] == 0) {
q.push(to);
dad[to] = node;
digit[to] = dig;
if (to == 0) {
break;
}
}
}
}
int node = 0;
vector<int> ans;
do {
ans.emplace_back(digit[node]);
node = dad[node];
} while (node != -1);
for (int i = (int)ans.size() - 1; i >= 0; --i) {
cout << ans[i];
}
cout << endl;
#ifdef LOCAL_DEFINE
cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
return 0;
}