Mai intai trebuie sa te autentifici.
Cod sursa(job #2149595)
Utilizator | Data | 2 martie 2018 19:21:00 | |
---|---|---|---|
Problema | Multiplu | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.17 kb |
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e6;
int l[MAXN + 1], t[MAXN + 1], v[MAXN + 1], hz[MAXN + 1];
char rez[MAXN + 1];
int main() {
FILE *fin, *fout;
int a, b, r, mod, st, dr, i, k, alfa, ok, n;
fin = fopen ("multiplu.in", "r");
fout = fopen ("multiplu.out", "w");
fscanf (fin, "%d%d", &a, &b);
mod = a * b;
while (b > 0) {
r = a % b;
a = b;
b = r;
}
mod = mod / a;
v[1] = 1;
l[1] = 1;
t[1] = -1;
hz[1] = 1;
n = ok = 0;
st = 1;
dr = 1;
while (st <= dr) {
for (i = 0; i <= 1; i++) {
k = (v[st] * 10 + i) % mod;
if (hz[k] == 0) {
dr++;
v[dr] = k;
t[dr] = st;
l[dr] = i;
hz[k] = 1 ;
if (v[dr] == 0) {
alfa = dr;
ok = 1;
break;
}
}
}
if (ok == 1) {
break;
}
st++;
}
while (alfa != -1) {
n++;
rez[n] = l[alfa] + 48;
alfa = t[alfa];
}
for (i = 1; i <= n / 2; i++) {
swap (rez[i], rez[n - i + 1]);
}
for (i = 1; i <= n; i++)
fprintf (fout, "%c", rez[i]);
fclose (fin);
fclose (fout);
return 0;
}