src/math/min_mod_linear/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../util/alias/num/lib.hpp" | ||
| 4 | |||
| 5 | namespace tifa_libs { | ||
| 6 | |||
| 7 | 12386807 | CEXP u32 min_mod_linear(u32 n, u32 m, u32 a, u32 b, u32 cnt = 1, u32 p = 1, u32 q = 1) NE { | |
| 8 |
2/2✓ Branch 0 taken 1064304 times.
✓ Branch 1 taken 11322503 times.
|
12386807 | if (!a) return b; |
| 9 |
2/2✓ Branch 0 taken 6030038 times.
✓ Branch 1 taken 5292465 times.
|
11322503 | if (cnt & 1) { |
| 10 |
2/2✓ Branch 0 taken 3002471 times.
✓ Branch 1 taken 3027567 times.
|
6030038 | if (b >= a) { |
| 11 | 3002471 | cu32 t = (m - b + a - 1) / a, c = (t - 1) * p + q; | |
| 12 |
2/2✓ Branch 0 taken 213105 times.
✓ Branch 1 taken 2789366 times.
|
3002471 | if (n <= c) return b; |
| 13 | 2789366 | n -= c, b += a * t - m; | |
| 14 | } | ||
| 15 | 5816933 | b = a - 1 - b; | |
| 16 | } else { | ||
| 17 |
2/2✓ Branch 0 taken 3157404 times.
✓ Branch 1 taken 2135061 times.
|
5292465 | if (b < m - a) { |
| 18 | 3157404 | cu32 t = (m - b - 1) / a, c = t * p; | |
| 19 |
2/2✓ Branch 0 taken 208205 times.
✓ Branch 1 taken 2949199 times.
|
3157404 | if (n <= c) return a * ((n - 1) / p) + b; |
| 20 | 2949199 | n -= c, b += a * t; | |
| 21 | } | ||
| 22 | 5084260 | b = m - 1 - b; | |
| 23 | } | ||
| 24 | 10901193 | cu32 d = m / a, c = min_mod_linear(n, a, m % a, b, ++cnt, (d - 1) * p + q, d * p + q); | |
| 25 |
2/2✓ Branch 0 taken 5084260 times.
✓ Branch 1 taken 5816933 times.
|
10901193 | retif_((cnt & 1), m - 1 - c, a - 1 - c); |
| 26 | } | ||
| 27 | |||
| 28 | } // namespace tifa_libs | ||
| 29 |