src/nt/residue/kth/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../../math/iroot/sqrt/lib.hpp" | ||
| 4 | #include "../../../math/qpow/mod/lib.hpp" | ||
| 5 | #include "../../gl/gcd/lib.hpp" | ||
| 6 | #include "../../inverse/lib.hpp" | ||
| 7 | |||
| 8 | namespace tifa_libs { | ||
| 9 | |||
| 10 | 88722 | CEXP auto kth_root(u64 a, u64 k, u64 p) NE { | |
| 11 | 88722 | std::optional<u64> ret; | |
| 12 |
4/4✓ Branch 0 taken 88507 times.
✓ Branch 1 taken 215 times.
✓ Branch 2 taken 177 times.
✓ Branch 3 taken 88330 times.
|
88722 | if (k > 0 && !(a % p)) { |
| 13 | 177 | ret.emplace(0); | |
| 14 | 177 | return ret; | |
| 15 | } | ||
| 16 | 88545 | k %= p - 1; | |
| 17 | 88545 | u64 g = gcd(k, p - 1); | |
| 18 |
2/2✓ Branch 1 taken 11964 times.
✓ Branch 2 taken 76581 times.
|
88545 | if (qpow_mod(a, (p - 1) / g, p) != 1) return ret; |
| 19 | 76581 | a = qpow_mod(a, inverse(k / g, (p - 1) / g), p); | |
| 20 | 53408 | auto pethr = [](u64 a, u64 p, u32 e, u64 m) NE { | |
| 21 | 53408 | u64 q = m - 1; | |
| 22 | 53408 | u32 s = 0; | |
| 23 |
2/2✓ Branch 0 taken 95528 times.
✓ Branch 1 taken 53408 times.
|
148936 | while (!(q % p)) q /= p, ++s; |
| 24 | 53408 | cu64 pe = qpow_mod(p, e, m); | |
| 25 | 53408 | u64 ans = qpow_mod(a, (mul_mod_u(pe - 1, inverse(q, pe), pe) * q + 1) / pe, m), c = 2; | |
| 26 |
2/2✓ Branch 1 taken 43203 times.
✓ Branch 2 taken 53408 times.
|
96611 | while (qpow_mod(c, (m - 1) / p, m) == 1) ++c; |
| 27 | 53408 | c = qpow_mod(c, q, m); | |
| 28 | 53408 | map<u64, u32> mp; | |
| 29 | 53408 | u64 _a = 1; | |
| 30 | 53408 | cu32 v = isqrt((s - e) * p) + 1; | |
| 31 | 53408 | u64 _m = qpow_mod(c, mul_mod_u(v, qpow_mod(p, s - 1, m - 1), m - 1), m); | |
| 32 |
2/2✓ Branch 2 taken 2569123 times.
✓ Branch 3 taken 53408 times.
|
2622531 | for (u32 i = 0; i <= v; ++i, _a = mul_mod_u(_a, _m, m)) mp[_a] = i; |
| 33 | 53408 | _m = inverse(qpow_mod(c, qpow_mod(p, s - 1, m - 1), m), m); | |
| 34 |
2/2✓ Branch 0 taken 36998 times.
✓ Branch 1 taken 53408 times.
|
90406 | flt_ (u32, i, e, s) { |
| 35 | 36998 | cu64 _ = mul_mod_u(a, inverse(qpow_mod(ans, pe, m), m), m); | |
| 36 | 36998 | u64 t = qpow_mod(_, qpow_mod(p, s - 1 - i, m - 1), m); | |
| 37 |
1/2✓ Branch 0 taken 1266356 times.
✗ Branch 1 not taken.
|
1266356 | flt_ (u32, j, 0, v + 1) { |
| 38 |
2/2✓ Branch 3 taken 36998 times.
✓ Branch 4 taken 1229358 times.
|
1266356 | if (mp.find(t) != end(mp)) { |
| 39 | 36998 | cu32 x = mp[t]; | |
| 40 | 36998 | ans = mul_mod_u(ans, qpow_mod(c, mul_mod_u(j + v * x, qpow_mod(p, i - e, m - 1), m - 1), m), m); | |
| 41 | 36998 | break; | |
| 42 | } | ||
| 43 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 1229358 times.
|
1229358 | t = mul_mod_u(t, _m, m), assert(j != v); |
| 44 | } | ||
| 45 | } | ||
| 46 | 106816 | return ans; | |
| 47 | 53408 | }; | |
| 48 |
2/2✓ Branch 0 taken 2438179 times.
✓ Branch 1 taken 76581 times.
|
2514760 | for (u64 d = 2; d * d <= g; ++d) { |
| 49 | 2438179 | u32 n = 0; | |
| 50 |
2/2✓ Branch 0 taken 12119 times.
✓ Branch 1 taken 2438179 times.
|
2450298 | while (!(g % d)) g /= d, ++n; |
| 51 |
2/2✓ Branch 0 taken 6997 times.
✓ Branch 1 taken 2431182 times.
|
2438179 | if (n) a = pethr(a, d, n, p); |
| 52 | } | ||
| 53 |
2/2✓ Branch 0 taken 46411 times.
✓ Branch 1 taken 30170 times.
|
76581 | if (g > 1) a = pethr(a, g, 1, p); |
| 54 | 76581 | ret.emplace(a); | |
| 55 | 76581 | return ret; | |
| 56 | } | ||
| 57 | |||
| 58 | } // namespace tifa_libs | ||
| 59 |