math/test/Sum_of_Floor_of_Linear.test.cpp

• View this file on GitHub
• Last update: 2023-07-25 00:50:50+07:00
• Problem: https://judge.yosupo.jp/problem/sum_of_floor_of_linear

Depends on

• Sum of Floor of Linear (math/floor_sum.hpp)

Code

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

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;

#include "math/floor_sum.hpp"

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cin.exceptions(cin.failbit);
  int tc;
  cin >> tc;
  while(tc--){
    int n, m, a, b;
    cin >> n >> m >> a >> b;
    cout << sum_of_floor<ll>(n, m, a, b) << '\n';
  }
}

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

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;

#line 2 "math/floor_sum.hpp"

// sum_{0 <= i < N} (ai + b) // m
template <typename T>
T sum_of_floor(T n, 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(y, a, m, (a - x % a) % a);
  return ret;
}

// verify www.codechef.com/viewsolution/36222026
// count x : ax + b mod m < yr, 0 <= x < xr
template <typename T>
T mod_affine_range_counting(T a, T b, T m, T xr, T yr) {
  assert(0 <= yr && yr <= m);
  return sum_of_floor(xr, m, a, b + m) - sum_of_floor(xr, m, a, b + m - yr);
}
#line 11 "math/test/Sum_of_Floor_of_Linear.test.cpp"

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cin.exceptions(cin.failbit);
  int tc;
  cin >> tc;
  while(tc--){
    int n, m, a, b;
    cin >> n >> m >> a >> b;
    cout << sum_of_floor<ll>(n, m, a, b) << '\n';
  }
}

Back to top page