fn choose2(n: Wrapping<u64>) -> Wrapping<u64>Examples found in repository?
crates/competitive/src/math/floor_sum.rs (line 29)
22pub fn floor_sum(n: u64, a: u64, b: u64, m: u64) -> u64 {
23 let mut ans = Wrapping(0u64);
24 let (mut n, mut m, mut a, mut b) = (Wrapping(n), m, a, b);
25 loop {
26 let br = BarrettReduction::<u64>::new(m);
27 if a >= m {
28 let (q, r) = br.div_rem(a);
29 ans += choose2(n) * q;
30 a = r;
31 }
32 if b >= m {
33 let (q, r) = br.div_rem(b);
34 ans += n * q;
35 b = r;
36 }
37 let y_max = (n * a + b).0;
38 if y_max < m {
39 break;
40 }
41 let (q, r) = br.div_rem(y_max);
42 n = Wrapping(q);
43 b = r;
44 swap(&mut m, &mut a);
45 }
46 ans.0
47}
48
49/// Sum of Floor of Linear mod 2^64
50///
51/// $$\sum_{i=l}^{r-1}\left\lfloor\frac{a\times i+b}{m}\right\rfloor$$
52pub fn floor_sum_i64(l: i64, r: i64, a: i64, b: i64, m: u64) -> i64 {
53 let mut ans = Wrapping(0i64);
54 let (n, m, a, b) = (
55 Wrapping((r - l) as u64),
56 m as i64,
57 a,
58 (Wrapping(l) * a + b).0,
59 );
60 let a = if a < 0 {
61 let r = a.rem_euclid(m);
62 let nc2 = choose2(n);
63 ans -= Wrapping(nc2.0 as _) * ((Wrapping(r) - a) / m);
64 r
65 } else {
66 a
67 };
68 let b = if b < 0 {
69 let r = b.rem_euclid(m);
70 ans -= Wrapping(n.0 as _) * ((Wrapping(r) - b) / m);
71 r
72 } else {
73 b
74 };
75 (ans + floor_sum(n.0, a as u64, b as u64, m as u64) as i64).0
76}