Pagini recente » Cod sursa (job #1931959) | Cod sursa (job #1084276) | Cod sursa (job #2976888) | Cod sursa (job #259434) | Cod sursa (job #2768457)
#include <fstream>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int a, b, m;
void read() {
ifstream f("multiplu.in");
f >> a >> b;
f.close();
}
int cmmmc(int a, int b) {
int ca = a, cb = b, r;
while (b) {
r = a % b;
a = b;
b = r;
}
return ca * cb / a;
}
int poz[2000001];
bool digit[2000001];
queue<int> Q;
vector<int> v;
void solve() {
int i, x;
m = cmmmc(a, b);
Q.push(1);
poz[1] = -1;
digit[1] = 1;
while (!Q.empty()) {
x = Q.front();
Q.pop();
if (x == 0)
break;
if (poz[(x * 10) % m] == 0) {
poz[(x * 10) % m] = x;
digit[(x * 10) % m] = 0;
Q.push((x * 10) % m);
}
if (poz[(x * 10 + 1) % m] == 0) {
poz[(x * 10 + 1) % m] = x;
digit[(x * 10 + 1) % m] = 1;
Q.push((x * 10 + 1) % m);
}
}
x = 0;
while (x != -1) {
v.emplace_back(digit[x]);
x = poz[x];
}
}
void output() {
int i;
ofstream g("multiplu.out");
for (i = v.size() - 1; i >= 0; i--)
g << v[i];
g.close();
}
int main() {
read();
solve();
output();
return 0;
}