src/math/qpow/tetra_mod/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../../nt/euler_phi/lib.hpp" | ||
| 4 | |||
| 5 | namespace tifa_libs { | ||
| 6 | namespace qtetra_mod_impl_ { | ||
| 7 | 290424 | CEXP u64 mpow(u64 a, u64 b, u64 m, u64& f) NE { | |
| 8 |
2/4✓ Branch 0 taken 290424 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 290424 times.
|
290424 | retif_((a == 1 || b == 0) [[unlikely]], 1); |
| 9 | 290424 | u64 v = 1, x = a, z = m; | |
| 10 | 290424 | f |= x >= z, x %= m; | |
| 11 | while (true) { | ||
| 12 |
2/2✓ Branch 0 taken 1453612 times.
✓ Branch 1 taken 2710192 times.
|
4163804 | if (b & 1) v *= x; |
| 13 |
2/2✓ Branch 0 taken 937484 times.
✓ Branch 1 taken 3226320 times.
|
4163804 | if (v >= z) f = 1, v %= m; |
| 14 |
2/2✓ Branch 0 taken 290424 times.
✓ Branch 1 taken 3873380 times.
|
4163804 | if (!(b >>= 1)) break; |
| 15 |
2/2✓ Branch 0 taken 2731015 times.
✓ Branch 1 taken 1142365 times.
|
3873380 | if ((x *= x) >= z) f = 1, x %= m; |
| 16 | } | ||
| 17 | 290424 | return v; | |
| 18 | } | ||
| 19 | |||
| 20 | 303149 | CEXP u64 qtetra(u64 a, u64 b, u64 m, u64& f) NE { | |
| 21 |
2/2✓ Branch 0 taken 202 times.
✓ Branch 1 taken 302947 times.
|
303149 | if (a == 0) return ~b & 1; |
| 22 |
2/2✓ Branch 0 taken 11276 times.
✓ Branch 1 taken 291671 times.
|
302947 | if (m == 1) return f = 1; |
| 23 |
4/4✓ Branch 0 taken 291478 times.
✓ Branch 1 taken 193 times.
✓ Branch 2 taken 152 times.
✓ Branch 3 taken 291326 times.
|
291671 | if (a == 1 || b == 0) return 1; |
| 24 |
2/2✓ Branch 0 taken 902 times.
✓ Branch 1 taken 290424 times.
|
291326 | if (b == 1) return a % m + (f |= (a >= m)) * m; |
| 25 | 290424 | cu64 z = qtetra(a, b - 1, euler_phi(m), f), r = mpow(a, z, m, f); | |
| 26 | 290424 | return r + f * m; | |
| 27 | } | ||
| 28 | } // namespace qtetra_mod_impl_ | ||
| 29 | |||
| 30 | 12725 | CEXP u64 qtetra_mod(u64 a, u64 b, u64 m) NE { | |
| 31 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 12725 times.
|
12725 | assert(m); |
| 32 | 12725 | u64 f = 0; | |
| 33 | 12725 | return qtetra_mod_impl_::qtetra(a, b, m, f) % m; | |
| 34 | } | ||
| 35 | |||
| 36 | } // namespace tifa_libs | ||
| 37 |