haar_lib/math/
enumerate_quotients.rs

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

haar_lib/math/
enumerate_quotients.rs
