src/math/exeuclid/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../math/qpow/basic/lib.hpp" | ||
| 4 | |||
| 5 | namespace tifa_libs { | ||
| 6 | |||
| 7 | // consider line s: y = (p * x + r) / q, 0 < x <= l | ||
| 8 | // result will add a when s cross with horizontal line | ||
| 9 | // result will add b when s cross with vertical line | ||
| 10 | template <class TIFA> | ||
| 11 | 383553 | CEXP TIFA exeuclid(i64 p, i64 q, i64 r, i64 l, TIFA CR a, TIFA CR b) NE { | |
| 12 | #pragma GCC diagnostic ignored "-Wfloat-conversion" | ||
| 13 | 8044197 | auto div = [](i64 a, i64 b, i64 c, i64 d) NE -> i64 { return (1.l * a * b + c) / d; }; | |
| 14 | #pragma GCC diagnostic warning "-Wfloat-conversion" | ||
| 15 | 8427947 | auto f = [&](auto&& f, i64 p, i64 q, i64 r, i64 l, cT_(TIFA) a, cT_(TIFA) b) NE -> TIFA { | |
| 16 |
2/2✓ Branch 0 taken 146638 times.
✓ Branch 1 taken 7897756 times.
|
8044394 | if (!l) return {}; |
| 17 |
2/2✓ Branch 0 taken 3757200 times.
✓ Branch 1 taken 4140556 times.
|
7897756 | if (p >= q) return f(f, p % q, q, r, l, a, qpow(a, u64(p / q), TIFA{}) * b); |
| 18 | 4140556 | ci64 m = div(l, p, r, q); | |
| 19 |
2/2✓ Branch 0 taken 236915 times.
✓ Branch 1 taken 3903641 times.
|
4140556 | if (!m) return qpow(b, (u64)l, TIFA{}); |
| 20 | 3903641 | ci64 cnt = l - div(q, m, -r - 1, p); | |
| 21 | 3903641 | return qpow(b, u64((q - r - 1) / p), TIFA{}) * a * f(f, q, p, (q - r - 1) % p, m - 1, b, a) * qpow(b, (u64)cnt, TIFA{}); | |
| 22 | }; | ||
| 23 | 383553 | return qpow(a, u64(r / q), TIFA{}) * f(f, p, q, r % q, l, a, b); | |
| 24 | } | ||
| 25 | |||
| 26 | } // namespace tifa_libs | ||
| 27 |