src/nt/dlog/exbsgs/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../gl/gcd/lib.hpp" | ||
| 4 | #include "../../inverse/lib.hpp" | ||
| 5 | #include "../naive/lib.hpp" | ||
| 6 | |||
| 7 | namespace tifa_libs { | ||
| 8 | |||
| 9 | // solve $a^x\equiv b \pmod m$ | ||
| 10 | 1818 | inline auto exbsgs(auto&& bsgs, u64 a, u64 b, u64 m) NE { | |
| 11 | 1818 | std::optional<u64> ret; | |
| 12 |
2/2✓ Branch 0 taken 307 times.
✓ Branch 1 taken 1511 times.
|
1818 | if (m < 64) { |
| 13 | 307 | ret = dlog_naive(a, b, m); | |
| 14 | 307 | return ret; | |
| 15 | } | ||
| 16 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1511 times.
|
1511 | if (a %= m, b %= m; b == 1) { |
| 17 | ✗ | ret.emplace(0); | |
| 18 | ✗ | return ret; | |
| 19 | } | ||
| 20 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1511 times.
|
1511 | if (!a) { |
| 21 | ✗ | if (!b) ret.emplace(1); | |
| 22 | ✗ | return ret; | |
| 23 | } | ||
| 24 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1511 times.
|
1511 | if (a == 1) { |
| 25 | ✗ | if (b == 1) ret.emplace(0); | |
| 26 | ✗ | return ret; | |
| 27 | } | ||
| 28 | 1511 | u64 cnt = 0, t = 1; | |
| 29 |
2/2✓ Branch 2 taken 711 times.
✓ Branch 3 taken 1048 times.
|
1759 | for (u64 d = gcd(a, m); d != 1; d = gcd(a, m)) { |
| 30 |
2/2✓ Branch 0 taken 463 times.
✓ Branch 1 taken 248 times.
|
711 | if (b % d) return ret; |
| 31 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 248 times.
|
248 | if (++cnt, b /= d, m /= d, (t *= a / d) %= m; b == t) { |
| 32 | ✗ | ret.emplace(cnt); | |
| 33 | ✗ | return ret; | |
| 34 | } | ||
| 35 | } | ||
| 36 |
2/2✓ Branch 3 taken 598 times.
✓ Branch 4 taken 450 times.
|
1048 | if (ret = bsgs(a, b * inverse(t, m), m); ret) ret.value() += cnt; |
| 37 | 1048 | return ret; | |
| 38 | } | ||
| 39 | |||
| 40 | } // namespace tifa_libs | ||
| 41 |