haar_lib/math/
enumerate_quotients.rs

1//! 商の列挙
2
3/// [`enumerate_quotients`]の結果
4#[derive(Copy, Debug, Eq, PartialEq, Clone, Hash)]
5pub struct Quotient {
6    /// `floor(N/x)`の値
7    pub q: u64,
8    /// `x`の最小値
9    pub from: u64,
10    /// `x`の最大値
11    pub to: u64,
12}
13
14/// 1以上N以下の自然数xについて`floor(N/x)`の取りうる値とそれを与えるxの範囲を列挙する。
15///
16/// **Time complexity** $O(\sqrt{N})$
17pub fn enumerate_quotients(n: u64) -> Vec<Quotient> {
18    let mut ret = vec![];
19
20    let mut k = 1;
21
22    while k * k <= n {
23        let q = n / k;
24        ret.push(Quotient { q, from: k, to: k });
25
26        k += 1;
27    }
28
29    while k <= n {
30        let q = n / k;
31        let u = n / q;
32        ret.push(Quotient { q, from: k, to: u });
33
34        k = u + 1;
35    }
36
37    ret.reverse();
38
39    ret
40}
41
42#[cfg(test)]
43mod tests {
44    use super::*;
45
46    #[test]
47    fn test() {
48        for n in 1..200 {
49            let ans = enumerate_quotients(n);
50            for Quotient { q, from, to } in ans {
51                assert_eq!(q, n / from);
52                assert_eq!(q, n / to);
53                assert_ne!(q, n / (to + 1));
54            }
55        }
56    }
57}
haar_lib/math/enumerate_quotients.rs

haar_lib/math/
enumerate_quotients.rs
