src/math/josephus/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../util/alias/num/lib.hpp" | ||
| 4 | |||
| 5 | namespace tifa_libs { | ||
| 6 | namespace josephus_impl_ { | ||
| 7 | // $O(m)$ | ||
| 8 | 100509955 | CEXP u64 j1(u64 n, u64 k, u64 m) NE { | |
| 9 |
2/2✓ Branch 0 taken 43052 times.
✓ Branch 1 taken 100466903 times.
|
100509955 | if (m == 1) return (k - 1) % n; |
| 10 | 100466903 | return (j1(n - 1, k, m - 1) + k) % n; | |
| 11 | } | ||
| 12 | // $O(k\log n)$ | ||
| 13 | 32592 | CEXP u64 j2(u64 n, u64 k, u64 m) NE { | |
| 14 |
2/2✓ Branch 0 taken 10978 times.
✓ Branch 1 taken 21614 times.
|
32592 | if (k == 1) return m - 1; |
| 15 | 21614 | u64 n2 = n - m + 1, ret = j1(n2, k, 1); | |
| 16 | 21614 | --m; | |
| 17 |
2/2✓ Branch 0 taken 60628 times.
✓ Branch 1 taken 28 times.
|
60656 | while (m) |
| 18 |
2/2✓ Branch 0 taken 21586 times.
✓ Branch 1 taken 39042 times.
|
60628 | if (cu64 _ = (n2 - ret) / (k - 1); m <= _) return (ret + m * k) % (n2 + m); |
| 19 | 39042 | else ret = (((ret + _ * k) % (n2 + _)) + k) % (n2 + _ + 1), n2 += _ + 1, m -= _ + 1; | |
| 20 | 28 | return ret; | |
| 21 | } | ||
| 22 | } // namespace josephus_impl_ | ||
| 23 | |||
| 24 | //! 0-based | ||
| 25 | // @return $m$-th executed person in Josephus problem | ||
| 26 | // with total_people = n, start_point = 0, skipped_number = k | ||
| 27 | 54030 | CEXP u64 Josephus(u64 n, u64 k, u64 m) NE { | |
| 28 |
3/6✓ Branch 0 taken 54030 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 54030 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 54030 times.
✗ Branch 5 not taken.
|
54030 | assert(m && k && m <= n); |
| 29 |
2/2✓ Branch 1 taken 21438 times.
✓ Branch 2 taken 32592 times.
|
54030 | retif_((m < k * (u32)std::bit_width(n)), josephus_impl_::j1(n, k, m), josephus_impl_::j2(n, k, m)); |
| 30 | } | ||
| 31 | |||
| 32 | } // namespace tifa_libs | ||
| 33 |