Sum of Floor of Linear
(Mathematics/sum_of_floor_of_linear.hpp)

• View this file on GitHub
• Last update: 2021-04-13 10:29:45+09:00
• Include: #include "Mathematics/sum_of_floor_of_linear.hpp"
• Link: https://tkmst201.github.io/Library/Mathematics/sum_of_floor_of_linear.hpp

概要

整数 $N, M, A, B$ に対して $\sum_{i=0}^{N-1} floor((A \times i + B) / M)$ を求めます。

関数

T sum_of_floor_of_linear(T N, T M, T A, T B)

$\sum_{i=0}^{N-1} floor((A \times i + B) / M)$ を返します。 ただし、 $N = 0$ のときは $0$ を返します。
ここで $floor(x)$ は $x$ を超えない最大の整数を表します。

制約

• T は int, unsigned int, long long, unsigned long long
• 式の値が T で表現可能 ( $(AN^2+B)/M$ が T で表現可能なら問題無し)
• $0 \leq N, A, B$
• $0 < M$

計算量

• $\mathcal{O}(\log{\min(M, A)})$

---

使用例

#include <bits/stdc++.h>
#include "Mathematics/sum_of_floor_of_linear.hpp"
using namespace std;

int main() {
	// n, m, a, b
	cout << tk::sum_of_floor_of_linear(5, 4, 2, 3) << endl; // sum[3/4, 5/4, 7/4, 9/4, 11/4] = 6
	cout << tk::sum_of_floor_of_linear(3, 2, 7, 4) << endl; // sum[4/2, 11/2, 18/2] = 16
	cout << tk::sum_of_floor_of_linear<long long>(100000, 1, 1, 0) << endl; // sum[...] = 4999950000
	cout << tk::sum_of_floor_of_linear(0, 1, 1, 100) << endl; // sum[] = 0
	cout << tk::sum_of_floor_of_linear(100, 3, 0, 100) << endl; // sum[33, ..., 33] = 3300
}

参考

2021/04/13: https://atcoder.jp/contests/practice2/editorial/579
2020/09/11: https://twitter.com/kyopro_friends/status/1304063876019793921?s=20
2020/09/10: https://qiita.com/HNJ/items/564f15316719209df73c

Verified with

• Test/sum_of_floor_of_linear.test.cpp

Code

#ifndef INCLUDE_GUARD_SUM_OF_FLOOR_OF_LINEAR_HPP
#define INCLUDE_GUARD_SUM_OF_FLOOR_OF_LINEAR_HPP

#include <utility>
#include <cassert>
#include <type_traits>

/**
 * @brief https://tkmst201.github.io/Library/Mathematics/sum_of_floor_of_linear.hpp
 */
namespace tk {
template<typename T>
T sum_of_floor_of_linear(T n, T m, T a, T b) {
	static_assert(std::is_integral<T>::value);
	assert(n >= 0);
	assert(m > 0);
	assert(a >= 0);
	assert(b >= 0);
	if (n == 0) return 0;
	const T qa = a / m, qb = b / m;
	T res = n * (n - 1) / 2 * qa + n * qb;
	a -= qa * m;
	b -= qb * m;
	if (a == 0) return res;
	const T q = (a * n + b) / m, r = (a * n + b) - q * m;
	return res + sum_of_floor_of_linear(q, a, m, r);
}
} // namespace tk


#endif // INCLUDE_GUARD_SUM_OF_FLOOR_OF_LINEAR_HPP

#line 1 "Mathematics/sum_of_floor_of_linear.hpp"



#include <utility>
#include <cassert>
#include <type_traits>

/**
 * @brief https://tkmst201.github.io/Library/Mathematics/sum_of_floor_of_linear.hpp
 */
namespace tk {
template<typename T>
T sum_of_floor_of_linear(T n, T m, T a, T b) {
	static_assert(std::is_integral<T>::value);
	assert(n >= 0);
	assert(m > 0);
	assert(a >= 0);
	assert(b >= 0);
	if (n == 0) return 0;
	const T qa = a / m, qb = b / m;
	T res = n * (n - 1) / 2 * qa + n * qb;
	a -= qa * m;
	b -= qb * m;
	if (a == 0) return res;
	const T q = (a * n + b) / m, r = (a * n + b) - q * m;
	return res + sum_of_floor_of_linear(q, a, m, r);
}
} // namespace tk

Back to top page