- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
int mysolve (int a, int b, int m) {
int n = (int) sqrt (m + .0) + 1;
int an = 1;
for (int i = n, t = a; i;) {
if (i & 1) {
an = (an * t) % m;
i -= 1;
} else {
t = (t * t) % m;
i >>= 1;
}
}
int *vals = (int*) malloc(m * sizeof(int));
memset(vals, -1, m * sizeof(int));
for (int i = 1, cur = an; i <= n; ++i) {
if (vals[cur] == -1) vals[cur] = i;
cur = (cur * an) % m;
}
for (int i = 0, cur = b; i <= n; ++i) {
if (vals[cur] != -1) {
int ans = vals[cur] * n - i;
if (ans < m) {
free(vals);
return ans;
}
}
cur = (cur * a) % m;
}
free(vals);
return -1;
}
Чото както тухло тут.
Вот держите, вспомнил своё олимпиАДное прошлое, перевёл на Сишку и оптимизировал вот этоу хуйнц: https://e-maxx.ru/algo/discrete_log
Чем больше модуль, ьем боьше жрёт память, дальше оптимизировать лень.
Мне кажется, что что-то я здесь сделал не так...
666_N33D135 02.06.2018 19:28 # −1
Здесь, кстати есть ошипка, но непонятно где.
666_N33D135 02.06.2018 19:33 # −1
Doctor_Who 03.06.2018 02:52 # 0
Надо же. Я думал, что только в Delphi такое оператороблядство.
Doctor_Who 02.06.2018 22:33 # 0
guest8 02.06.2018 22:44 # −999
guest8 02.06.2018 23:16 # −999
guest8 02.06.2018 23:54 # −999
syoma 03.06.2018 07:58 # 0
666_N33D135 03.06.2018 08:10 # 0
666_N33D135 03.06.2018 08:22 # 0
syoma 03.06.2018 09:56 # 0
666_N33D135 03.06.2018 07:46 # 0
666_N33D135 03.06.2018 07:47 # 0
guest8 03.06.2018 19:30 # −999
guest8 03.06.2018 19:33 # −999
666_N33D135 03.06.2018 19:36 # 0
666_N33D135 03.06.2018 19:36 # 0
Это, кстати, в C99 убрали.
666_N33D135 03.06.2018 19:38 # 0
bormand 03.06.2018 20:35 # +2
guest8 03.06.2018 20:39 # −999
g0cTb 03.06.2018 20:38 # 0
bormand 03.06.2018 20:40 # 0
guest8 03.06.2018 23:56 # −999
AnalMixer 04.06.2018 00:01 # 0
bormand 03.06.2018 20:43 # 0