Struct nekolib::math::HarmonicFloorSum

pub struct HarmonicFloorSum { /* private fields */ }

$\sum_{i=1}^n \lfloor m/i\rfloor$ および $\sum_{i=1}^n (m\bmod i)$.

Idea

$\lfloor m/\bullet\rfloor$ の値は $O(\sqrt{m})$ 通りである。 $i\in[q_l, q_r]$ において $\lfloor m/i\rfloor$ の値が共通であるとき、 $\sum_{i=q_l}^{q_r} \lfloor m/i\rfloor$ の値は簡単に求められる。 また、この範囲で $(m\bmod i)$ は等差数列を成すことから、 $\sum_{i=q_l}^{q_r} (m\bmod i)$ も簡単に求められる。 前計算でこれらの累積和を求めておき、差分計算によってクエリ処理を行う。

Notes

考察を進めれば $\sum_{i=1}^n \lfloor\frac{m}{ai+b}\rfloor$ を求めることも可能？

Complexity

$O(\sqrt{m})$ preprocess, $O(1)$ query time.

Examples

use nekolib::math::HarmonicFloorSum;

let m = 100;
let hs = HarmonicFloorSum::new(m);
assert_eq!(hs.quot(1..=m), (1..=m).map(|i| m / i).sum());
assert_eq!(hs.rem(1..=m), (1..=m).map(|i| m % i).sum());

let n = 60;
assert_eq!(hs.quot(..=n), (1..=n).map(|i| m / i).sum());

Implementations

impl HarmonicFloorSum

pub fn new(m: usize) -> Self

前処理を行う。

Examples

use nekolib::math::HarmonicFloorSum;

let m = 100;
let hs = HarmonicFloorSum::new(m);

pub fn quot(&self, r: impl RangeBounds<usize>) -> usize

$\sum_{i=s}^e \lfloor m/i\rfloor$ を返す。

$\sum_{i=s}^{\infty} \lfloor m/i\rfloor = \sum_{i=s}^m \lfloor m/i\rfloor$ なので、上限を指定しない場合は $m$ までの和を求める。下限を指定しない場合は $1$ からの和を求める。

Examples

use nekolib::math::HarmonicFloorSum;

let m = 100;
let hs = HarmonicFloorSum::new(m);
assert_eq!(hs.quot(1..=m), (1..=m).map(|i| m / i).sum());
assert_eq!(hs.quot(..), (1..=m).map(|i| m / i).sum());
assert_eq!(hs.quot(1..=m), hs.quot(1..=m + 1));

pub fn rem(&self, r: impl RangeBounds<usize>) -> usize

$\sum_{i=s}^e (m\bmod i)$ を返す。

下限を指定しない場合は $1$ からの和を求める。

Panics

$\sum_{i=s}^{\infty} (m\bmod i) = \infty$ なので、上限が Unbounded の場合は panic する。

Examples

use nekolib::math::HarmonicFloorSum;

let m = 100;
let hs = HarmonicFloorSum::new(m);
assert_eq!(hs.rem(1..=m), (1..=m).map(|i| m % i).sum());
assert_eq!(hs.rem(..=m), (1..=m).map(|i| m % i).sum());
assert_ne!(hs.rem(1..=m), hs.rem(1..=m + 1)); // m % (m + 1) = m > 0

use nekolib::math::HarmonicFloorSum;
let m = 100;
let hs = HarmonicFloorSum::new(m);
let infty = hs.rem(1..); // diverges

Trait Implementations

impl Clone for HarmonicFloorSum

fn clone(&self) -> HarmonicFloorSum

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for HarmonicFloorSum

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.