verify/floor_sum.test.cpp

View this file on GitHub
Last update: 2024-12-28 00:04:13+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 "../Utility/template.hpp"
#include "../Math/floor_sum.hpp"

int main() {
    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/floor_sum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/sum_of_floor_of_linear"
#line 1 "Utility/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define rrep(i, s, t) for (ll i = (ll)(t) - 1; i >= (ll)(s); i--)
#define all(x) begin(x), end(x)

#define TT template <typename T>
TT using vec = vector<T>;
template <class T1, class T2> bool chmin(T1 &x, T2 y) {
    return x > y ? (x = y, true) : false;
}
template <class T1, class T2> bool chmax(T1 &x, T2 y) {
    return x < y ? (x = y, true) : false;
}
struct io_setup {
    io_setup() {
        ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        cout << fixed << setprecision(15);
    }
} io_setup;

/*
@brief verify用テンプレート
*/
#line 1 "Math/floor_sum.hpp"
ll floor_sum(ll n, ll m, ll a, ll b) {
    assert(0 <= n && n < (1LL << 32));
    assert(1 <= m && m < (1LL << 32));
    using ull = unsigned long long;

    ull ans = 0;
    if (a < 0) {
        ull a2 = (a % m + m) % m;
        ans -= 1ULL * n * (n - 1) / 2 * ((a2 - a) / m);
        a = a2;
    }
    if (b < 0) {
        ull b2 = (b % m + m) % m;
        ans -= 1ULL * n * ((b2 - b) / m);
        b = b2;
    }

    auto uns_fl = [](ull n, ull m, ull a, ull b) {
        ull res = 0;
        while (1) {
            if (a >= m) {
                res += n * (n - 1) / 2 * (a / m);
                a %= m;
            }
            if (b >= m) {
                res += n * (b / m);
                b %= m;
            }

            ull y = a * n + b;
            if (y < m) break;
            n = (ull)(y / m);
            b = (ull)(y % m);
            swap(m, a);
        }
        return res;
    };

    return ans + uns_fl(n, m, a, b);
}

/*
@brief floor_sum
@docs doc/floor_sum.md
*/
#line 4 "verify/floor_sum.test.cpp"

int main() {
    int T;
    cin >> T;
    while(T--) {
        ll N, M, A, B;
        cin >> N >> M >> A >> B;
        cout << floor_sum(N, M, A, B) << '\n';
    }
}