Function floor_sum

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

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/math/sum_of_floor_of_linear.rs (line 11)

pub fn sum_of_floor_of_linear(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, t, query: [(u64, u64, u64, u64)]);
    for (n, m, a, b) in query.take(t) {
        writeln!(writer, "{}", floor_sum(n, a, b, m)).ok();
    }
}

crates/competitive/src/math/floor_sum.rs (line 75)

pub fn floor_sum_i64(l: i64, r: i64, a: i64, b: i64, m: u64) -> i64 {
    let mut ans = Wrapping(0i64);
    let (n, m, a, b) = (
        Wrapping((r - l) as u64),
        m as i64,
        a,
        (Wrapping(l) * a + b).0,
    );
    let a = if a < 0 {
        let r = a.rem_euclid(m);
        let nc2 = choose2(n);
        ans -= Wrapping(nc2.0 as _) * ((Wrapping(r) - a) / m);
        r
    } else {
        a
    };
    let b = if b < 0 {
        let r = b.rem_euclid(m);
        ans -= Wrapping(n.0 as _) * ((Wrapping(r) - b) / m);
        r
    } else {
        b
    };
    (ans + floor_sum(n.0, a as u64, b as u64, m as u64) as i64).0
}