数学/sum of floor of linear
(test/math/floor_sum.test.cpp)

• View this file on GitHub
• Last update: 2023-02-25 01:48:23+09:00
• Problem: https://judge.yosupo.jp/problem/sum_of_floor_of_linear

Depends on

• sum of floor of linear (include/emthrm/math/floor_sum.hpp)

Code

/*
 * @title 数学/sum of floor of linear
 *
 * verification-helper: PROBLEM https://judge.yosupo.jp/problem/sum_of_floor_of_linear
 */

#include <iostream>

#include "emthrm/math/floor_sum.hpp"

int main() {
  int t;
  std::cin >> t;
  while (t--) {
    int n, m, a, b;
    std::cin >> n >> m >> a >> b;
    std::cout << emthrm::floor_sum(a, b, m, n) << '\n';
  }
  return 0;
}

#line 1 "test/math/floor_sum.test.cpp"
/*
 * @title 数学/sum of floor of linear
 *
 * verification-helper: PROBLEM https://judge.yosupo.jp/problem/sum_of_floor_of_linear
 */

#include <iostream>

#line 1 "include/emthrm/math/floor_sum.hpp"



#include <utility>

namespace emthrm {

long long floor_sum(long long a, long long b, long long m, long long n) {
  long long res = 0;
  if (a < 0) {
    long long nxt_a = a % m;
    if (nxt_a < 0) nxt_a += m;
    res -= n * (n - 1) / 2 * ((nxt_a - a) / m);
    a = nxt_a;
  }
  if (b < 0) {
    long long nxt_b = b % m;
    if (nxt_b < 0) nxt_b += m;
    res -= n * ((nxt_b - b) / m);
    b = nxt_b;
  }
  while (true) {
    if (a >= m) {
      res += n * (n - 1) / 2 * (a / m);
      a %= m;
    }
    if (b >= m) {
      res += n * (b / m);
      b %= m;
    }
    const long long y_max = a * n + b;
    if (y_max < m) break;
    b = y_max % m;
    n = y_max / m;
    std::swap(a, m);
  }
  return res;
}

}  // namespace emthrm


#line 10 "test/math/floor_sum.test.cpp"

int main() {
  int t;
  std::cin >> t;
  while (t--) {
    int n, m, a, b;
    std::cin >> n >> m >> a >> b;
    std::cout << emthrm::floor_sum(a, b, m, n) << '\n';
  }
  return 0;
}

Back to top page