src/nt/carmichael/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../math/qpow/basic/lib.hpp" | ||
| 4 | #include "../gl/lcm/lib.hpp" | ||
| 5 | #include "../pfactors/lib.hpp" | ||
| 6 | |||
| 7 | namespace tifa_libs { | ||
| 8 | |||
| 9 | 360 | inline u64 carmichael(spn<std::pair<u64, u32>> pf_exp) NE { | |
| 10 | 360 | u64 ans = 1; | |
| 11 |
6/6✓ Branch 5 taken 326 times.
✓ Branch 6 taken 40 times.
✓ Branch 7 taken 290 times.
✓ Branch 8 taken 36 times.
✓ Branch 13 taken 366 times.
✓ Branch 14 taken 360 times.
|
726 | for (auto CR[p, e] : pf_exp) ans = lcm(ans, (p - 1) * qpow(p, e - (p == 2 && e >= 3) - 1)); |
| 12 | 360 | return ans; | |
| 13 | } | ||
| 14 | inline u64 carmichael(u64 n) NE { return carmichael(pf_exp(n)); } | ||
| 15 | |||
| 16 | } // namespace tifa_libs | ||
| 17 |