src/nt/dlog/naive/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../../math/mul_mod/lib.hpp" | ||
| 4 | |||
| 5 | namespace tifa_libs { | ||
| 6 | |||
| 7 | 307 | inline auto dlog_naive(u64 a, u64 b, u64 m) NE { | |
| 8 | 307 | std::optional<u64> ret; | |
| 9 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 307 times.
|
307 | retif_((m == 0) [[unlikely]], ret); |
| 10 |
4/4✓ Branch 0 taken 285 times.
✓ Branch 1 taken 22 times.
✓ Branch 2 taken 65 times.
✓ Branch 3 taken 220 times.
|
307 | if (a %= m, b %= m; m == 1 || b == 1) { |
| 11 | 87 | ret.emplace(0); | |
| 12 | 87 | return ret; | |
| 13 | } | ||
| 14 |
2/2✓ Branch 0 taken 46 times.
✓ Branch 1 taken 174 times.
|
220 | if (!a) { |
| 15 |
2/2✓ Branch 0 taken 26 times.
✓ Branch 1 taken 20 times.
|
46 | if (!b) ret.emplace(1); |
| 16 | 46 | return ret; | |
| 17 | } | ||
| 18 |
2/2✓ Branch 0 taken 39 times.
✓ Branch 1 taken 135 times.
|
174 | if (a == 1) { |
| 19 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 39 times.
|
39 | if (b == 1) ret.emplace(0); |
| 20 | 39 | return ret; | |
| 21 | } | ||
| 22 |
2/2✓ Branch 0 taken 783 times.
✓ Branch 1 taken 83 times.
|
866 | flt_ (u32, i, 0, (u32)m, pow_a = 1) { |
| 23 |
2/2✓ Branch 0 taken 52 times.
✓ Branch 1 taken 731 times.
|
783 | if (pow_a == b) { |
| 24 | 52 | ret.emplace(i); | |
| 25 | 52 | return ret; | |
| 26 | } | ||
| 27 | 731 | pow_a = (u32)mul_mod_u(pow_a, a, m); | |
| 28 | } | ||
| 29 | 83 | return ret; | |
| 30 | } | ||
| 31 | |||
| 32 | } // namespace tifa_libs | ||
| 33 |