Trait nekolib::math::CommonQuot

pub trait CommonQuot {
    type Output;

    // Required method
    fn common_quot(self) -> Self::Output;
}

商が共通の区間の列挙。

$\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

• ABC 044 D

Required Associated Types

type Output

Required Methods

fn common_quot(self) -> Self::Output

Implementations on Foreign Types

impl CommonQuot for u32

type Output = CommonQuotStruct<u32>

fn common_quot(self) -> Self::Output

impl CommonQuot for u128

type Output = CommonQuotStruct<u128>

fn common_quot(self) -> Self::Output

impl CommonQuot for u8

type Output = CommonQuotStruct<u8>

fn common_quot(self) -> Self::Output

impl CommonQuot for usize

type Output = CommonQuotStruct<usize>

fn common_quot(self) -> Self::Output

impl CommonQuot for u64

type Output = CommonQuotStruct<u64>

fn common_quot(self) -> Self::Output

impl CommonQuot for u16

type Output = CommonQuotStruct<u16>

fn common_quot(self) -> Self::Output

Implementors