Function floor_sum 

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

等差数列の各項を m で割った商（床）の総和を返します。

次の値を O(log m) で計算します。

sum_{i = 0}^{n - 1} floor((a * i + b) / m)

n は項数（和の対象は i = 0..n の半開区間）、m は除数、a は係数、b は定数項です。 すべての引数は u64 なので非負であり、m は正でなければなりません。

計算量は O(log m) です。戻り値は u128 ですが、非常に大きな入力では総和が u128 に 収まらないことがあります。正しい結果を得るには総和が u128 に収まり、計算途中の値も u128 の範囲内であることが必要です。積の計算には u128 を使います。

Panics

m が 0 の場合は panic します。

Examples

use atcoder::floor_sum::floor_sum;

let sum = floor_sum(6, 5, 3, 2);

// floor(2 / 5) + floor(5 / 5) + floor(8 / 5)
// + floor(11 / 5) + floor(14 / 5) + floor(17 / 5)
// = 0 + 1 + 1 + 2 + 2 + 3
assert_eq!(sum, 9);