はじめに この記事では、floor sum を計算する漸化式の導出方法を紹介します。 floor sum は、次の形の和を計算量 $O(\log M)$ で計算するアルゴリズムです。 $$f(N, M, A, B) = \sum_{k=0}^{N-1} \left\lfloor \frac{Ak + B}{M} \right\rfloor$$ ここで、$N…