Всегда писал Миллера-Рабина для чисел в пределах [1, 2 ^ 31 - 1]. И вчера на одном OJ попалась задача,где нужно писать вышеупомянутый тест на простоту для чисел [1, 2 ^ 63 - 1].Все отлично, но вот возводить в степень за log(n) не получается.При возведении промежуточные результаты выходят за пределы long long.Не подскажите ли, знающие люди, как ето можно сделать ?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 154 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 146 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 133 |
| 10 | cry | 130 |
кроме того, там ограничения на N до 2^63 - 1, такчто без длинной арифметики или её подобия не обойтись. есть тупой алгоритм бинарного деления, сложность та же что при использовании бинарного умножения (но оно тут не применимо в чистом виде, из-за ограничений)
int Mod(int a, int b) { int k = 0; while (a > b) { b <<= 1; k++; } while (k >= 0) { if (a >= b) a -= b; b >>= 1; k--; } return a; }
UPD: вместо int - любой твой тип (длинное число)
ну и длинку надо делать по основанию 2^16 или 2^32
Бинарное умножение по модулю. binmult(a,b,mod) {
if (b == 1) x == a; else { x = } return x; }
Бинарное умножение по модулю. Разделяй и властвуй) long long binmultmod(long long a, long long b, long long mod) { long long x; if (a == 0 || b == 0) return 0; if (b==1){ x=a; } else{ x=binmultmod(a, b/2, mod); x=(x+x)%mod; if (b%2==1) x=(x+a)%mod; } return x; }