test/math/Sum_of_Floor_of_Linear.test.cpp

View this file on GitHub
Last update: 2023-11-18 01:32:49+09:00
Problem: https://judge.yosupo.jp/problem/sum_of_floor_of_linear

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/sum_of_floor_of_linear"

#include"../../template/template.hpp"
#include"../../math/floor_sum.hpp"

using namespace lib;

int main(){
	int t; cin >> t;
	while(t--){
		ll n,m,a,b;
		cin >> n >> m >> a >> b;
		cout << floor_sum(n, m, a, b) << '\n';
	}
}

#line 1 "test/math/Sum_of_Floor_of_Linear.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/sum_of_floor_of_linear"

#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
#line 5 "test/math/Sum_of_Floor_of_Linear.test.cpp"

using namespace lib;

int main(){
	int t; cin >> t;
	while(t--){
		ll n,m,a,b;
		cin >> n >> m >> a >> b;
		cout << floor_sum(n, m, a, b) << '\n';
	}
}