Trait nekolib::math::common_quot::CommonQuot
source · pub trait CommonQuot {
type Output;
// Required method
fn common_quot(self) -> Self::Output;
}Expand description
商が共通の区間の列挙。
$\gdef\floor#1{\lfloor#1\rfloor}$ 以下の条件を満たす $(i_l, i_r)$ を $i_l$ の昇順に列挙する。
- $1\le i_l \wedge i_r \le n$,
- $j\in [i_l, i_r] \implies \floor{n/j} = \floor{n/i_l}$, and
- $j\notin [i_l, i_r] \implies j=0 \vee \floor{n/j} \ne \floor{n/i_l}$.
Complexity
$O(\sqrt{n})$ time, $O(1)$ space.
Examples
use nekolib::math::CommonQuot;
assert_eq!(
60_u64.common_quot().collect::<Vec<_>>(),
[
(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (7, 7), (8, 8),
(9, 10), (11, 12), (13, 15), (16, 20), (21, 30), (31, 60)
]
);