Pagini recente » Cod sursa (job #985192) | Cod sursa (job #2540970) | Cod sursa (job #124675) | Cod sursa (job #161072) | Cod sursa (job #1436068)
#include <fstream>
#include <string>
#include <queue>
#include <vector>
#include <algorithm>
#define LIM 2000001
using namespace std;
vector <int> s;
ifstream fi("multiplu.in");
ofstream fo("multiplu.out");
queue <int> q;
int a,b,xa,xb, r[LIM], pre[LIM], val[LIM];
int cmmdc(int a, int b) {
if (!b) return a;
return cmmdc(b, a % b);
}
int main() {
fi >> a >> b;
int cmmmc = (a*b)/cmmdc(a,b);
int lastRest = 0;
q.push(1);
r[1] = 1;
pre[1] = 0;
val[1] = 1;
while (!q.empty()) {
int auxRest = q.front();
q.pop();
int x1 = (auxRest * 10) % cmmmc;
int x2 = (auxRest * 10 + 1) % cmmmc;
if (!r[x1]) {
r[x1] = 1;
pre[x1] = auxRest;
val[x1] = 0;
q.push(x1);
}
if (!r[x2]) {
r[x2] = 1;
pre[x2] = auxRest;
val[x2] = 1;
q.push(x2);
}
if (!x1) {
s.push_back(0);
lastRest = auxRest;
break;
}
if (!x2) {
s.push_back(1);
lastRest = auxRest;
break;
}
}
while (lastRest) {
s.push_back(val[lastRest]);
lastRest = pre[lastRest];
}
reverse(s.begin(), s.end());
for (vector <int>::iterator it = s.begin(); it != s.end(); it++) {
fo << *it;
}
return 0;
}