Floor Sum
(math/floor_sum.hpp)

• View this file on GitHub
• Last update: 2023-11-18 01:32:49+09:00
• Include: #include "math/floor_sum.hpp"

説明

次を求める.

$\displaystyle f(n, m, a, b) = \sum^{n-1}_{i=0} \left\lfloor \frac{ai + b}{m} \right\rfloor$

$a, b$ が負でもよい. ただし, $a, b$ が非負であることが保証されている場合は, コードを短縮できる.

Depends on

• テンプレート (template/template.hpp)

Verified with

• test/math/Sum_of_Floor_of_Linear.test.cpp

Code

#pragma once
#include "../template/template.hpp"

namespace lib {
using namespace std;

ll floor_sum(ll n, ll m, ll a, ll b){
	if (n == 0) return 0;
	ll ret = 0;
	
	/* if [a >= 0 and b >= 0] is guaranteed, ignore from here */
	if (a < 0){
		ll a2 = a % m;
		if (a2 < 0) a2 += m;
		ret -= (ll)n * (n-1) / 2 * ((a2 - a) / m);
		a = a2;
	}
	if (b < 0){
		ll b2 = b % m;
		if (b2 < 0) b2 += m;
		ret -= (ll)n * ((b2 - b) / m);
		b = b2;
	}
	/* till here */

	if (a >= m){
		ret += n * (n-1) / 2 * (a / m);
		a %= m;
	}
	if (b >= m){
		ret += n * (b / m);
		b %= m;
	}
	ll y = (a * n + b) / m;
	ll z = (a * n + b) % m;
	return ret + floor_sum(y, a, m, z);
}

}  // namespace lib

#line 2 "template/template.hpp"

#include <bits/stdc++.h>

#define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++)
#define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--)
#define all(v) v.begin(), v.end()

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <typename T> bool chmin(T &a, const T &b) {
    if (a <= b) return false;
    a = b;
    return true;
}
template <typename T> bool chmax(T &a, const T &b) {
    if (a >= b) return false;
    a = b;
    return true;
}

namespace lib {

using namespace std;

}  // namespace lib

// using namespace lib;
#line 3 "math/floor_sum.hpp"

namespace lib {
using namespace std;

ll floor_sum(ll n, ll m, ll a, ll b){
	if (n == 0) return 0;
	ll ret = 0;
	
	/* if [a >= 0 and b >= 0] is guaranteed, ignore from here */
	if (a < 0){
		ll a2 = a % m;
		if (a2 < 0) a2 += m;
		ret -= (ll)n * (n-1) / 2 * ((a2 - a) / m);
		a = a2;
	}
	if (b < 0){
		ll b2 = b % m;
		if (b2 < 0) b2 += m;
		ret -= (ll)n * ((b2 - b) / m);
		b = b2;
	}
	/* till here */

	if (a >= m){
		ret += n * (n-1) / 2 * (a / m);
		a %= m;
	}
	if (b >= m){
		ret += n * (b / m);
		b %= m;
	}
	ll y = (a * n + b) / m;
	ll z = (a * n + b) % m;
	return ret + floor_sum(y, a, m, z);
}

}  // namespace lib

Back to top page