Verify/SumofFloorofLinear.test.cpp

View this file on GitHub
Last update: 2023-02-11 22:28:05+08: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 "../Number_Theory/SumofFloor.hpp"

void solve() {
    i64 n, m, a, b;
    std::cin >> n >> m >> a >> b;
    auto ans = sum_of_floor<i64>(n, m, a, b);
    std::cout << ans << '\n';
    return;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int T;
    std::cin >> T;

    while (T--) {
        solve();
    }

    return 0;
}

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

#line 2 "Number_Theory/SumofFloor.hpp"

#line 2 "Template/Template.hpp"

#include <bits/stdc++.h>

using i64 = std::int64_t;
#line 4 "Number_Theory/SumofFloor.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 4 "Verify/SumofFloorofLinear.test.cpp"

void solve() {
    i64 n, m, a, b;
    std::cin >> n >> m >> a >> b;
    auto ans = sum_of_floor<i64>(n, m, a, b);
    std::cout << ans << '\n';
    return;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int T;
    std::cin >> T;

    while (T--) {
        solve();
    }

    return 0;
}