test/verify/yosupo-sum-of-floor-of-linear.test.cpp

• View this file on GitHub
• Last update: 2026-08-10 14:29:01+00:00
• Problem: https://judge.yosupo.jp/problem/sum_of_floor_of_linear

Depends on

• Sum of Floor of Linear (一次関数の床関数の和) (math/number-theory/sum-of-floor-of-linear.hpp)

Code

// clang-format off
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/sum_of_floor_of_linear
// clang-format on

#include <iostream>

#include "../../math/number-theory/sum-of-floor-of-linear.hpp"

using namespace std;

int main() {
  int T;
  cin >> T;
  while (T--) {
    long long N, M, A, B;
    cin >> N >> M >> A >> B;
    cout << sum_of_floor_of_linear(N, M, A, B) << "\n";
  }
}

#line 1 "test/verify/yosupo-sum-of-floor-of-linear.test.cpp"
// clang-format off
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/sum_of_floor_of_linear
// clang-format on

#include <iostream>

#line 2 "math/number-theory/sum-of-floor-of-linear.hpp"

template <typename T>
T sum_of_floor_of_linear(const T& n, const T& m, T a, T b) {
  T ret = 0;
  if (a >= m) ret += (n - 1) * n * (a / m) / 2, a %= m;
  if (b >= m) ret += n * (b / m), b %= m;
  T y = (a * n + b) / m;
  if (y == 0) return ret;
  T x = y * m - b;
  ret += (n - (x + a - 1) / a) * y;
  ret += sum_of_floor_of_linear(y, a, m, (a - x % a) % a);
  return ret;
}
#line 8 "test/verify/yosupo-sum-of-floor-of-linear.test.cpp"

using namespace std;

int main() {
  int T;
  cin >> T;
  while (T--) {
    long long N, M, A, B;
    cin >> N >> M >> A >> B;
    cout << sum_of_floor_of_linear(N, M, A, B) << "\n";
  }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	2 ms	4 MB
g++	random_00	AC	47 ms	4 MB
g++	random_01	AC	169 ms	4 MB
g++	random_02	AC	170 ms	4 MB
g++	random_03	AC	85 ms	4 MB
g++	random_04	AC	36 ms	4 MB
g++	small_00	AC	30 ms	4 MB
g++	small_01	AC	98 ms	4 MB
g++	small_02	AC	81 ms	4 MB
g++	small_03	AC	51 ms	4 MB
g++	small_04	AC	25 ms	4 MB
clang++	example_00	AC	2 ms	4 MB
clang++	random_00	AC	44 ms	4 MB
clang++	random_01	AC	157 ms	4 MB
clang++	random_02	AC	184 ms	4 MB
clang++	random_03	AC	118 ms	4 MB
clang++	random_04	AC	57 ms	4 MB
clang++	small_00	AC	41 ms	4 MB
clang++	small_01	AC	141 ms	4 MB
clang++	small_02	AC	112 ms	4 MB
clang++	small_03	AC	52 ms	4 MB
clang++	small_04	AC	35 ms	4 MB

Back to top page