Pagini recente » Cod sursa (job #92012) | Cod sursa (job #2074107) | Cod sursa (job #596800) | Cod sursa (job #2589089) | Cod sursa (job #1551761)
#include <cstdio>
using namespace std;
#define MaxN 2000000
int Q[MaxN];
int qStart, qEnd;
int numDigs[MaxN];
int father[MaxN];
bool digit[MaxN];
int gcd(int A, int B) {
if (!B) {
return A;
}
return gcd(B, A % B);
}
void print(const int rest) {
if (numDigs[rest] > 1) {
print(father[rest]);
}
putchar(digit[rest] + '0');
}
int main(void) {
freopen("multiplu.in", "r", stdin);
freopen("multiplu.out", "w", stdout);
int A, B;
scanf("%d%d", &A, &B);
fclose(stdin);
A = (A * B) / gcd(A, B);
if (A == 1) {
putchar('1');
fclose(stdout);
return 0;
}
numDigs[1] = 1;
digit[1] = 1;
Q[0] = 1;
qStart = 0;
qEnd = 1;
while (qStart < qEnd && !numDigs[0]) {
const int restCurr = Q[qStart++];
for (int i = 0; i <= 1; i++) {
const int restNou = (restCurr * 10 + i) % A;
if (!numDigs[restNou]) {
numDigs[restNou] = numDigs[restCurr] + 1;
father[restNou] = restCurr;
digit[restNou] = i;
Q[qEnd++] = restNou;
}
}
}
print(0);
fclose(stdout);
return 0;
}