Pagini recente » Cod sursa (job #2263705) | Cod sursa (job #1400364) | Cod sursa (job #966719) | Cod sursa (job #462674) | Cod sursa (job #1570891)
#include <fstream>
#include <algorithm>
#include <queue>
using namespace std;
ifstream in("multiplu.in");
ofstream out("multiplu.out");
const int MAX_N = 2000000;
int P[1 + MAX_N];
queue < int > Q;
int gcd(int a, int b) {
if(b == 0) {
return a;
}
return gcd(b, a%b);
}
int lcm(int a, int b) {
return a * b / gcd(a, b);
}
void remakePath(int u) {
if(u == 1) {
out << 1;
return;
}
else {
remakePath(abs(P[u]));
if(P[u] < 0) {
out << 1;
}
else {
out << 0;
}
}
}
int main() {
int a, b, n, i, u, v;
in >> a >> b;
n = lcm(a, b);
Q.push(1);
while(!Q.empty()) {
u = Q.front();
Q.pop();
if(u == 0) {
break;
}
v = (u * 10) % n;
if(P[v] == 0) {
P[v] = u;
Q.push(v);
}
v = (u * 10 + 1) % n;
if(P[v] == 0) {
P[v] = -u;
Q.push(v);
}
}
remakePath(0);
return 0;
}