src/nt/norm_fact/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../math/ds/gint/lib.hpp" | ||
| 4 | #include "../../math/qpow/basic/lib.hpp" | ||
| 5 | #include "../../math/qpow/mod/lib.hpp" | ||
| 6 | #include "../pfactors/lib.hpp" | ||
| 7 | |||
| 8 | namespace tifa_libs { | ||
| 9 | namespace norm_fact_impl_ { | ||
| 10 | 4694 | CEXP gint<i128, -1> nfp(u64 p) NE { | |
| 11 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 4694 times.
|
4694 | if (p % 4 == 3) return {-1, -1}; |
| 12 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 4694 times.
|
4694 | if (p == 2) return {1, 1}; |
| 13 | 4694 | i64 x = 1; | |
| 14 | while (true) | ||
| 15 |
2/2✓ Branch 2 taken 4694 times.
✓ Branch 3 taken 3012 times.
|
7706 | if (cu64 z = qpow_mod(u64(++x), (p - 1) / 4, p); mul_mod_u(z, z, p) == p - 1) { |
| 16 | 4694 | x = (i64)z; | |
| 17 | 4694 | break; | |
| 18 | 3012 | } | |
| 19 | 4694 | i64 y = 1, k = i64(((i128)x * x + 1) / p); | |
| 20 |
2/2✓ Branch 0 taken 11192 times.
✓ Branch 1 taken 4694 times.
|
15886 | while (k > 1) { |
| 21 | 11192 | i64 b = x % k, d = y % k; | |
| 22 |
2/2✓ Branch 0 taken 3610 times.
✓ Branch 1 taken 7582 times.
|
11192 | if (b < 0) b += k; |
| 23 |
2/2✓ Branch 0 taken 4952 times.
✓ Branch 1 taken 6240 times.
|
11192 | if (b * 2 > k) b -= k; |
| 24 |
2/2✓ Branch 0 taken 3076 times.
✓ Branch 1 taken 8116 times.
|
11192 | if (d < 0) d += k; |
| 25 |
2/2✓ Branch 0 taken 2923 times.
✓ Branch 1 taken 8269 times.
|
11192 | if (d * 2 > k) d -= k; |
| 26 | 11192 | ci64 xx = i64(((i128)x * b + (i128)y * d) / k), yy = i64(((i128)x * d - (i128)y * b) / k); | |
| 27 | 11192 | x = xx, y = yy, k = i64(((i128)x * x + (i128)y * y) / p); | |
| 28 | } | ||
| 29 | 4694 | return {x, y}; | |
| 30 | } | ||
| 31 | 5690 | CEXP vec<gint<i128, -1>> nfpp(u64 p, u32 e) NE { | |
| 32 | using G = gint<i128, -1>; | ||
| 33 |
3/4✓ Branch 0 taken 398 times.
✓ Branch 1 taken 5292 times.
✓ Branch 2 taken 398 times.
✗ Branch 3 not taken.
|
6486 | if (p % 4 == 3) return {e & 1 ? 0 : (i64)qpow(p, e / 2)}; |
| 34 |
2/2✓ Branch 0 taken 598 times.
✓ Branch 1 taken 4694 times.
|
6488 | if (p == 2) return {qpow(G{1, 1}, e)}; |
| 35 | 4694 | const G _ = nfp(p); | |
| 36 | 14082 | vec<G> pows(e + 1), ret(e + 1); | |
| 37 | 4694 | pows[0] = 1; | |
| 38 |
2/2✓ Branch 3 taken 11223 times.
✓ Branch 4 taken 4694 times.
|
15917 | flt_ (u32, i, 1, e + 1) pows[i] = pows[i - 1] * _; |
| 39 |
2/2✓ Branch 5 taken 15917 times.
✓ Branch 6 taken 4694 times.
|
20611 | flt_ (u32, i, 0, e + 1) ret[i] = pows[i] * conj(pows[e - i]); |
| 40 | 4694 | return ret; | |
| 41 | 4694 | } | |
| 42 | 3317 | CEXP vec<gint<i128, -1>> nf(u64 n) NE { | |
| 43 | using G = gint<i128, -1>; | ||
| 44 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 3317 times.
|
3317 | if (!n) return {{}}; |
| 45 | 3317 | auto const pe = pf_exp(n); | |
| 46 |
2/2✓ Branch 7 taken 8573 times.
✓ Branch 8 taken 1671 times.
|
10244 | for (auto CR[p, e] : pe) |
| 47 |
4/4✓ Branch 0 taken 2176 times.
✓ Branch 1 taken 6397 times.
✓ Branch 2 taken 1646 times.
✓ Branch 3 taken 530 times.
|
8573 | if (p % 4 == 3 && (e & 1)) return {}; |
| 48 | 3342 | vec<G> ret{G{1}}; | |
| 49 |
2/2✓ Branch 7 taken 5690 times.
✓ Branch 8 taken 1671 times.
|
7361 | for (auto CR[p, e] : pe) { |
| 50 | 5690 | vec<G> nxt; | |
| 51 |
2/2✓ Branch 6 taken 682886 times.
✓ Branch 7 taken 5690 times.
|
688576 | for (cvec<G> now = nfpp(p, e); auto CR g1 : ret) |
| 52 |
2/2✓ Branch 7 taken 1459560 times.
✓ Branch 8 taken 682886 times.
|
2148136 | for (auto CR g2 : now) nxt.push_back(g1 * g2); |
| 53 | 5690 | ret = nxt; | |
| 54 | 5690 | } | |
| 55 |
2/2✓ Branch 5 taken 778345 times.
✓ Branch 6 taken 1671 times.
|
780016 | for (auto& g : ret) |
| 56 |
6/6✓ Branch 4 taken 1382902 times.
✓ Branch 5 taken 612572 times.
✓ Branch 7 taken 604557 times.
✓ Branch 8 taken 778345 times.
✓ Branch 9 taken 1217129 times.
✓ Branch 10 taken 778345 times.
|
1995474 | while (g.real() <= 0 || g.imag() < 0) g = {-g.imag(), g.real()}; |
| 57 | 1671 | return ret; | |
| 58 | 3317 | } | |
| 59 | } // namespace norm_fact_impl_ | ||
| 60 | |||
| 61 | // find all non-negative integer pair (x, y) s.t. $x^2+y^2=n$ in lexicographic order | ||
| 62 | 3318 | CEXP vecptuu norm_fact(u64 n) NE { | |
| 63 |
2/2✓ Branch 0 taken 1 time.
✓ Branch 1 taken 3317 times.
|
3320 | if (!n) return {{0, 0}}; |
| 64 | 3317 | vecptuu ans; | |
| 65 |
2/2✓ Branch 6 taken 778345 times.
✓ Branch 7 taken 3317 times.
|
781662 | for (auto& g : norm_fact_impl_::nf(n)) |
| 66 |
2/2✓ Branch 4 taken 256 times.
✓ Branch 5 taken 778089 times.
|
781662 | if (ans.emplace_back(g.real(), g.imag()); !g.imag()) ans.emplace_back(g.imag(), g.real()); |
| 67 | 3317 | tifa_libs::sort(ans); | |
| 68 | 3317 | return ans; | |
| 69 | 3317 | } | |
| 70 | |||
| 71 | } // namespace tifa_libs | ||
| 72 |