Pagini recente » Cod sursa (job #816860) | Cod sursa (job #263580) | Cod sursa (job #1082668) | Cod sursa (job #2021388) | Cod sursa (job #3356036)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
int q[2000005];
int pr[2000005];
bitset<2000005> val;
long long get_gcd(long long a, long long b) {
while(b) {
a %= b;
swap(a, b);
}
return a;
}
int main() {
long long a, b;
fin >> a >> b;
long long k = (a * b) / get_gcd(a, b);
memset(pr, -1, sizeof(pr));
int head = 0, tail = 0;
q[tail++] = 1 % k;
pr[1 % k] = -2;
val[1 % k] = 1;
while(head < tail) {
int curr = q[head++];
if(curr == 0) {
break;
}
int next0 = (curr * 10) % k;
if(pr[next0] == -1) {
pr[next0] = curr;
val[next0] = 0;
q[tail++] = next0;
if(next0 == 0) break;
}
int next1 = (curr * 10 + 1) % k;
if(pr[next1] == -1) {
pr[next1] = curr;
val[next1] = 1;
q[tail++] = next1;
if(next1 == 0) break;
}
}
vector<int> ans;
int curr = 0;
while(curr != -2) {
ans.push_back(val[curr]);
curr = pr[curr];
}
reverse(ans.begin(), ans.end());
for(int i = 0; i < ans.size(); ++i) {
fout << ans[i];
}
fout << "\n";
fin.close();
fout.close();
return 0;
}