fn choose2(n: Wrapping<u64>) -> Wrapping<u64>Examples found in repository?
crates/competitive/src/math/floor_sum.rs (line 25)
18pub fn floor_sum(n: u64, a: u64, b: u64, m: u64) -> u64 {
19 let mut ans = Wrapping(0u64);
20 let (mut n, mut m, mut a, mut b) = (Wrapping(n), m, a, b);
21 loop {
22 let br = BarrettReduction::<u64>::new(m);
23 if a >= m {
24 let (q, r) = br.div_rem(a);
25 ans += choose2(n) * q;
26 a = r;
27 }
28 if b >= m {
29 let (q, r) = br.div_rem(b);
30 ans += n * q;
31 b = r;
32 }
33 let y_max = (n * a + b).0;
34 if y_max < m {
35 break;
36 }
37 let (q, r) = br.div_rem(y_max);
38 n = Wrapping(q);
39 b = r;
40 swap(&mut m, &mut a);
41 }
42 ans.0
43}
44
45/// $$\min(\{(a\times i+b)\bmod m\mid0\leq i<n\}\cup\{m\})$$
46pub fn min_of_mod_of_linear(mut n: u64, mut a: u64, mut b: u64, mut m: u64) -> u64 {
47 if n == 0 {
48 return m;
49 }
50 if a >= m {
51 a %= m;
52 }
53 if b >= m {
54 b %= m;
55 }
56 let mut ans = Wrapping(0u64);
57 let mut pos = true;
58 let mut p = 1;
59 let mut q = 1;
60 while a != 0 {
61 let e = if pos { a } else { m } - 1;
62 let r = m % a;
63 let d = m - b;
64 if if pos { b + 1 } else { d } > a {
65 let t = (d - 1) / a + u64::from(pos);
66 let c = (t - u64::from(pos)) * p + if pos { q } else { 0 };
67 if n <= c {
68 if !pos {
69 ans -= Wrapping(a) * Wrapping((n - 1) / p);
70 }
71 break;
72 }
73 n -= c;
74 if pos {
75 b = a * t - d;
76 } else {
77 b += a * t;
78 }
79 }
80 if r != 0 {
81 let x = m / a * p + q;
82 q = x;
83 p = x - p;
84 }
85 if pos {
86 ans += e;
87 } else {
88 ans -= e;
89 }
90 m = a;
91 a = r;
92 b = e - b;
93 pos = !pos;
94 }
95 if pos { (ans + b).0 } else { (ans - b).0 }
96}
97
98/// Sum of Floor of Linear mod 2^64
99///
100/// $$\sum_{i=l}^{r-1}\left\lfloor\frac{a\times i+b}{m}\right\rfloor$$
101pub fn floor_sum_i64(l: i64, r: i64, a: i64, b: i64, m: u64) -> i64 {
102 let mut ans = Wrapping(0i64);
103 let (n, m, a, b) = (
104 Wrapping((r - l) as u64),
105 m as i64,
106 a,
107 (Wrapping(l) * a + b).0,
108 );
109 let a = if a < 0 {
110 let r = a.rem_euclid(m);
111 let nc2 = choose2(n);
112 ans -= Wrapping(nc2.0 as _) * ((Wrapping(r) - a) / m);
113 r
114 } else {
115 a
116 };
117 let b = if b < 0 {
118 let r = b.rem_euclid(m);
119 ans -= Wrapping(n.0 as _) * ((Wrapping(r) - b) / m);
120 r
121 } else {
122 b
123 };
124 (ans + floor_sum(n.0, a as u64, b as u64, m as u64) as i64).0
125}