src/nt/gl/rgcd/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../../math/iroot/sqrt/lib.hpp" | ||
| 4 | #include "../../lsieve/impl1/lib.hpp" | ||
| 5 | |||
| 6 | namespace tifa_libs { | ||
| 7 | |||
| 8 | class rgcd { | ||
| 9 | struct ls_rgcd { | ||
| 10 | struct F3 { | ||
| 11 | u32 a, b, c; | ||
| 12 | 319937400 | CEXP F3(u32 _a = 0, u32 _b = 0, u32 _c = 0) NE : a(_a), b(_b), c(_c) {} | |
| 13 | }; | ||
| 14 | vec<F3> fs; | ||
| 15 | |||
| 16 | protected: | ||
| 17 | 60 | CEXPE ls_rgcd(u32 n) NE : fs(n) { | |
| 18 |
1/2✓ Branch 0 taken 30 times.
✗ Branch 1 not taken.
|
30 | if (n > 1) fs[1] = {1, 1, 1}; |
| 19 | 30 | } | |
| 20 | |||
| 21 | 19937370 | CEXP void prime(u32 p) NE { fs[p] = {1, 1, p}; } | |
| 22 | 181035600 | CEXP void coprime(u32 i, u32 j) NE { | |
| 23 | 181035600 | F3& now = fs[i * j]; | |
| 24 | 181035600 | now = fs[i]; | |
| 25 |
2/2✓ Branch 0 taken 84922410 times.
✓ Branch 1 taken 96113190 times.
|
181035600 | if ((now.a *= j) > now.b) swap(now.a, now.b); |
| 26 |
2/2✓ Branch 0 taken 3860190 times.
✓ Branch 1 taken 177175410 times.
|
181035600 | if (now.b > now.c) swap(now.b, now.c); |
| 27 | 181035600 | } | |
| 28 | 99026970 | CEXP void not_coprime(u32 i, u32 j) NE { | |
| 29 | 99026970 | F3& now = fs[i * j]; | |
| 30 | 99026970 | now = fs[i]; | |
| 31 |
2/2✓ Branch 0 taken 49813530 times.
✓ Branch 1 taken 49213440 times.
|
99026970 | if ((now.a *= j) > now.b) swap(now.a, now.b); |
| 32 |
2/2✓ Branch 0 taken 7448250 times.
✓ Branch 1 taken 91578720 times.
|
99026970 | if (now.b > now.c) swap(now.b, now.c); |
| 33 | 99026970 | } | |
| 34 | }; | ||
| 35 | |||
| 36 | lsieve<ls_rgcd> s; | ||
| 37 | vvecu g_; | ||
| 38 | |||
| 39 | public: | ||
| 40 | 90 | CEXPE rgcd(u32 n) NE : s(n), g_(isqrt(n) + 1, vvecu::value_type(isqrt(n) + 1)) { | |
| 41 |
2/2✓ Branch 1 taken 94860 times.
✓ Branch 2 taken 30 times.
|
94890 | flt_ (u32, i, 1, (u32)g_.size()) { |
| 42 | 94860 | g_[i][0] = g_[0][i] = g_[i][i] = i; | |
| 43 |
2/2✓ Branch 6 taken 149926230 times.
✓ Branch 7 taken 94860 times.
|
150021090 | flt_ (u32, j, 1, i) g_[i][j] = g_[j][i] = g_[j][i % j]; |
| 44 | } | ||
| 45 | 30 | } | |
| 46 | |||
| 47 | 121 | CEXP u32 operator()(u32 x, u32 y) CNE { | |
| 48 |
7/10✓ Branch 1 taken 121 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 121 times.
✗ Branch 5 not taken.
✓ Branch 8 taken 69 times.
✓ Branch 9 taken 52 times.
✓ Branch 11 taken 69 times.
✗ Branch 12 not taken.
✓ Branch 13 taken 69 times.
✓ Branch 14 taken 52 times.
|
121 | if (assert(x < s.fs.size() && y < s.fs.size()); x < g_.size() && y < g_.size()) return g_[x][y]; |
| 49 | 52 | u32 ans = 1, _; | |
| 50 |
3/4✓ Branch 6 taken 156 times.
✗ Branch 7 not taken.
✓ Branch 10 taken 156 times.
✓ Branch 11 taken 52 times.
|
208 | for (cu32 i : {s.fs[x].a, s.fs[x].b, s.fs[x].c}) y /= (_ = i < g_.size() ? g_[i][y % i] : (y % i == 0) * (i - 1) + 1), ans *= _; |
| 51 | 52 | return ans; | |
| 52 | } | ||
| 53 | }; | ||
| 54 | |||
| 55 | } // namespace tifa_libs | ||
| 56 |