src/nt/period_fib/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../math/iroot/sqrt/lib.hpp" | ||
| 4 | #include "../gl/lcm/lib.hpp" | ||
| 5 | |||
| 6 | namespace tifa_libs { | ||
| 7 | |||
| 8 | //! Not the minimal | ||
| 9 | 5 | CEXP u64 period_fib(u32 n) NE { | |
| 10 | 12 | auto g = [](u64 p) NE -> u64 { | |
| 11 | static CEXP arr<u32, 6> _{0, 1, 3, 8, 6, 20}; | ||
| 12 |
2/2✓ Branch 0 taken 9 times.
✓ Branch 1 taken 3 times.
|
12 | if (p <= 5) return _[p]; |
| 13 |
3/4✓ Branch 0 taken 2 times.
✓ Branch 1 taken 1 time.
✗ Branch 2 not taken.
✓ Branch 3 taken 2 times.
|
3 | retif_((p % 5 == 1 || p % 5 == 4), p - 1, (p + 1) * 2); |
| 14 | }; | ||
| 15 | |||
| 16 | 5 | u64 res = 1; | |
| 17 |
2/2✓ Branch 1 taken 33076 times.
✓ Branch 2 taken 5 times.
|
33081 | flt_ (u32, i, 2, isqrt(n) + 1) |
| 18 |
2/2✓ Branch 0 taken 10 times.
✓ Branch 1 taken 33066 times.
|
33076 | if (n % i == 0) { |
| 19 | 10 | n /= i; | |
| 20 | 10 | u64 x = g(i), _ = n; | |
| 21 |
2/2✓ Branch 0 taken 21 times.
✓ Branch 1 taken 10 times.
|
31 | while (n % i == 0) n /= i; |
| 22 | 10 | x *= _ / n, res = lcm(res, x); | |
| 23 | } | ||
| 24 |
2/2✓ Branch 0 taken 2 times.
✓ Branch 1 taken 3 times.
|
5 | if (n > 1) res = lcm(res, g(n)); |
| 25 | 5 | return res; | |
| 26 | } | ||
| 27 | |||
| 28 | } // namespace tifa_libs | ||
| 29 |