verify/library_checker/number_theory/sum_of_floor_of_linear.test.cpp

View this file on GitHub
Last update: 2024-11-09 02:03:28+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 "../../../src/template/template.hpp"
#include "../../../src/math/floor_sum.hpp"
int main(void) {
    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 "verify/library_checker/number_theory/sum_of_floor_of_linear.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/sum_of_floor_of_linear"
#line 2 "src/template/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
    SetupIO() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout << fixed << setprecision(30);
    }
} setup_io;
#line 3 "src/math/floor_sum.hpp"
constexpr long long floor_sum(const long long n, const long long m, long long a, long long b) {
    long long res = 0;
    if(a >= m) res += (n - 1) * n * (a / m) / 2, a %= m;
    if(b >= m) res += n * (b / m), b %= m;
    const long long y = (a * n + b) / m;
    if(y == 0) return res;
    const long long x = y * m - b;
    res += (n - (x + a - 1) / a) * y;
    res += floor_sum(y, a, m, (a - x % a) % a);
    return res;
}
#line 4 "verify/library_checker/number_theory/sum_of_floor_of_linear.test.cpp"
int main(void) {
    int t;
    cin >> t;
    while(t--) {
        ll n, m, a, b;
        cin >> n >> m >> a >> b;
        cout << floor_sum(n, m, a, b) << '\n';
    }
}