Pagini recente » Cod sursa (job #1785169) | Cod sursa (job #53470) | Cod sursa (job #1007409) | Cod sursa (job #1217153) | Cod sursa (job #199353)
Cod sursa(job #199353)
#include <cstdio>
#include <cstring>
#define MAX_N 2000005
#define INF 0x3f3f3f3f
int n;
int a, b;
int best[MAX_N];
int par[MAX_N];
char cif[MAX_N];
char num[MAX_N];
int q[MAX_N], qb, qe;
inline int gcd(int a, int b) {
return !b ? a : gcd(b, a%b);
}
int main() {
freopen("multiplu.in", "r", stdin);
freopen("multiplu.out", "w", stdout);
scanf("%d %d", &a, &b);
n = a * b / gcd(a, b);
memset(best, INF, sizeof(best));
best[1 % n] = 1;
cif[1 % n] = 1;
q[qb = qe = 1] = 1 % n;
while (best[0] == INF) {
int val = q[qb++];
if (best[val] + 1 < best[(val * 10) % n]) {
par[(val * 10) % n] = val;
cif[(val * 10) % n] = 0;
best[(val * 10) % n] = best[val] + 1;
q[++qe] = (val * 10) % n;
}
if (best[val] + 1 < best[(val * 10 + 1) % n]) {
par[(val * 10 + 1) % n] = val;
cif[(val * 10 + 1) % n] = 1;
best[(val * 10 + 1) % n ] = best[val] + 1;
q[++qe] = (val * 10 + 1) % n;
}
}
int r = 0;
for (int i = best[0]; i; --i) {
num[i] = cif[r];
r = par[r];
}
for (int i = 1; i <= best[0]; ++i)
printf("%d", num[i]);
}