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)
    ]
);

See also

Required Associated Types§

Required Methods§

source

fn common_quot(self) -> Self::Output

Implementations on Foreign Types§

source§

impl CommonQuot for u32

source§

impl CommonQuot for u128

source§

impl CommonQuot for u8

source§

impl CommonQuot for usize

source§

impl CommonQuot for u64

source§

impl CommonQuot for u16

Implementors§