Pagini recente » Monitorul de evaluare | Cod sursa (job #1962495) | Monitorul de evaluare | Cod sursa (job #2018268) | Cod sursa (job #2262964)
#include <fstream>
#include <queue>
#include <bitset>
#define MAXN 2000004
using namespace std;
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
inline int cmmdc(int a, int b) {
int r;
do {
r = a % b;
a = b;
b = r;
} while (r);
return a;
}
bitset <MAXN> val, fr;
queue <int> Q;
int pred[MAXN];
void Afis(int poz) {
if (pred[poz]) {
Afis(pred[poz]);
fout << val[poz];
}
else
fout << poz;
}
int multiplu;
inline void Solve() {
Q.push(1); pred[1] = 0; val[1] = 1; fr[1] = 1;
int x, val1, val2, modulo;
while (!Q.empty()) {
x = Q.front();
val1 = x * 10 + 0;
if (val1 % multiplu == 0) {
val[0] = 0; pred[0] = x;
Afis(0);
return;
}
else {
modulo = val1 % multiplu;
if (!fr[modulo]) {
fr[modulo] = 1;
pred[modulo] = x; val[modulo] = 0;
Q.push(modulo);
}
}
val2 = x * 10 + 1;
if (val2 % multiplu == 0) {
val[0] = 1; pred[0] = x;
Afis(0);
return;
}
else {
modulo = val2 % multiplu;
if (!fr[modulo]) {
fr[modulo] = 1;
val[modulo] = 1; pred[modulo] = x;
Q.push(modulo);
}
}
Q.pop();
}
}
inline void Read() {
int A, B, div;
fin >> A >> B;
div = cmmdc(A, B);
multiplu = (1LL * A * B) / div;
}
int main () {
Read();
Solve();
fin.close(); fout.close(); return 0;
}