Pagini recente » Cod sursa (job #2056900) | Cod sursa (job #1907657) | Cod sursa (job #1486625) | Cod sursa (job #2133149) | Cod sursa (job #3218929)
#include <iostream>
#include <fstream>
#include <queue>
#include <bitset>
#include <algorithm>
using namespace std;
const int MAX = 2000000;
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
bitset<MAX + 1> bifat, cif;
int pre[MAX + 1];
void reconstruct(int x) {
if (pre[x]!=0) reconstruct(pre[x]);
fout << cif[x];
}
int main() {
int A, B;
fin >> A >> B;
queue<int> Q;
Q.push(1);
cif[1] = 1;
bifat[1] = 1;
int cmmmc = A / __gcd(A, B) * B;
while (!Q.empty()) {
int val = Q.front();
if (val == 0) {
reconstruct(val);
break;
}
Q.pop();
if (val * 10 <= MAX && !bifat[(val * 10)%cmmmc]) {
bifat[(val * 10)%cmmmc] = 1;
cif[(val * 10)%cmmmc] = 0;
pre[(val * 10)%cmmmc] = val;
Q.push((val * 10)%cmmmc);
}
if (val * 10 + 1 <= MAX && !bifat[(val * 10 + 1)%cmmmc]) {
bifat[(val * 10 + 1)%cmmmc] = 1;
cif[(val * 10 + 1)%cmmmc] = 1;
pre[(val * 10 + 1)%cmmmc] = val;
Q.push((val * 10 + 1)%cmmmc);
}
}
return 0;
}