Skip to main content

floor_sum

competitive::math::floor_sum

Function floor_sum 

Source 
pub fn floor_sum(n: u64, a: u64, b: u64, m: u64) -> u64
Expand description

Sum of Floor of Linear mod 2^64

$$\sum_{i=0}^{n-1}\left\lfloor\frac{a\times i+b}{m}\right\rfloor$$

Examples found in repository?
crates/library_checker/src/number_theory/sum_of_floor_of_linear.rs (line 9)
5pub fn sum_of_floor_of_linear(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(t, query: [(u64, u64, u64, u64); iter t]);
8    for (n, m, a, b) in query {
9        pp!(floor_sum(n, a, b, m));
10    }
11}
More examples
Hide additional examples
crates/competitive/src/math/floor_sum.rs (line 124)
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}