nekolib/math/
common_quot.rs

1//! 商が共通の区間の列挙。
2
3/// 商が共通の区間の列挙。
4///
5/// $\gdef\floor#1{\\lfloor#1\\rfloor}$
6/// 以下の条件を満たす $(i\_l, i\_r)$ を $i\_l$ の昇順に列挙する。
7/// - $1\\le i\_l \\wedge i\_r \\le n$,
8/// - $j\\in [i\_l, i\_r] \\implies \\floor{n/j} = \\floor{n/i\_l}$, and
9/// - $j\\notin [i\_l, i\_r] \\implies j=0 \\vee \\floor{n/j} \\ne \\floor{n/i\_l}$.
10///
11/// # Complexity
12/// $O(\\sqrt{n})$ time, $O(1)$ space.
13///
14/// # Examples
15/// ```
16/// use nekolib::math::CommonQuot;
17///
18/// assert_eq!(
19///     60_u64.common_quot().collect::<Vec<_>>(),
20///     [
21///         (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (7, 7), (8, 8),
22///         (9, 10), (11, 12), (13, 15), (16, 20), (21, 30), (31, 60)
23///     ]
24/// );
25/// ```
26///
27/// ## See also
28/// - [ABC 044 D](https://atcoder.jp/contests/abc044/tasks/arc060_b)
29pub trait CommonQuot {
30    type Output;
31    fn common_quot(self) -> Self::Output;
32}
33
34pub struct CommonQuotStruct<I> {
35    i: I,
36    n: I,
37}
38
39macro_rules! impl_common_quot_uint {
40    ( $($ty:ty)* ) => { $(
41        impl CommonQuot for $ty {
42            type Output = CommonQuotStruct<$ty>;
43            fn common_quot(self) -> Self::Output {
44                Self::Output { i: 0, n: self }
45            }
46        }
47        impl Iterator for CommonQuotStruct<$ty> {
48            type Item = ($ty, $ty);
49            fn next(&mut self) -> Option<($ty, $ty)> {
50                if self.i >= self.n {
51                    return None;
52                }
53                self.i += 1;
54                if self.i <= self.n {
55                    let l = self.i;
56                    let q = self.n / l;
57                    let r = self.n / q;
58                    self.i = r;
59                    return Some((l, r));
60                }
61                None
62            }
63        }
64    )* };
65}
66
67impl_common_quot_uint! { u8 u16 u32 u64 u128 usize }
68
69#[test]
70fn test_small() {
71    let suite: &[(u64, &[(u64, u64)])] = &[
72        (0, &[]),
73        (1, &[(1, 1)]),
74        (2, &[(1, 1), (2, 2)]),
75        (3, &[(1, 1), (2, 3)]),
76        (4, &[(1, 1), (2, 2), (3, 4)]),
77        (5, &[(1, 1), (2, 2), (3, 5)]),
78        (10, &[(1, 1), (2, 2), (3, 3), (4, 5), (6, 10)]),
79        (100, &[
80            (1, 1),
81            (2, 2),
82            (3, 3),
83            (4, 4),
84            (5, 5),
85            (6, 6),
86            (7, 7),
87            (8, 8),
88            (9, 9),
89            (10, 10),
90            (11, 11),
91            (12, 12),
92            (13, 14),
93            (15, 16),
94            (17, 20),
95            (21, 25),
96            (26, 33),
97            (34, 50),
98            (51, 100),
99        ]),
100        (200, &[
101            (1, 1),
102            (2, 2),
103            (3, 3),
104            (4, 4),
105            (5, 5),
106            (6, 6),
107            (7, 7),
108            (8, 8),
109            (9, 9),
110            (10, 10),
111            (11, 11),
112            (12, 12),
113            (13, 13),
114            (14, 14),
115            (15, 15),
116            (16, 16),
117            (17, 18),
118            (19, 20),
119            (21, 22),
120            (23, 25),
121            (26, 28),
122            (29, 33),
123            (34, 40),
124            (41, 50),
125            (51, 66),
126            (67, 100),
127            (101, 200),
128        ]),
129    ];
130    for (n, expected) in suite {
131        let actual: Vec<_> = n.common_quot().collect();
132        assert_eq!(&actual, expected);
133    }
134}
135
136#[test]
137fn test() {
138    let n_max = 10000_u64;
139    for n in 1..=n_max {
140        let mut l = 1;
141        let mut expected = vec![];
142        while l <= n {
143            let r = (l..).take_while(|&r| n / r == n / l).last().unwrap();
144            expected.push((l, r));
145            l = r + 1;
146        }
147        let actual: Vec<_> = n.common_quot().collect();
148        if n == 60 {
149            eprintln!("{:?}", actual);
150        }
151        assert_eq!(actual, expected);
152    }
153}
154
155#[test]
156fn overflow() {
157    for i in (1_u32..=1000)
158        .flat_map(|i| [i.wrapping_neg(), 2_u32.pow(16) * (2_u32.pow(16) - i)])
159    {
160        let actual: Vec<_> = i.common_quot().collect();
161        let expected: Vec<_> = (i as u64)
162            .common_quot()
163            .map(|(l, r)| (l as u32, r as u32))
164            .collect();
165        assert_eq!(actual, expected);
166    }
167}
168
169#[test]
170fn overflow_exhaustive() {
171    for i in u8::MIN..=u8::MAX {
172        eprintln!("{}_u8", i);
173        let actual: Vec<_> = i.common_quot().collect();
174        let expected: Vec<_> =
175            (i as u32).common_quot().map(|(l, r)| (l as u8, r as u8)).collect();
176        assert_eq!(actual, expected);
177    }
178    for i in u16::MIN..=u16::MAX {
179        eprintln!("{}_u16", i);
180        let actual: Vec<_> = i.common_quot().collect();
181        let expected: Vec<_> = (i as u32)
182            .common_quot()
183            .map(|(l, r)| (l as u16, r as u16))
184            .collect();
185        assert_eq!(actual, expected);
186    }
187}
nekolib/math/common_quot.rs

nekolib/math/
common_quot.rs
