test/yosupo/sum_of_floor_of_linear.test.cpp

• View this file on GitHub
• Last update: 2024-01-08 19:16:08+09:00
• Problem: https://judge.yosupo.jp/problem/sum_of_floor_of_linear

Depends on

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

Code

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

#include "../../math/number-theory/floor_sum.hpp"

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

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

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

#line 2 "math/number-theory/floor_sum.hpp"

long long floor_sum(long long n, long long m, long long a, long long b) {
    long long sum = 0;
    if (a >= m) {
        sum += (a / m) * n * (n - 1) / 2;
        a %= m;
    }
    if (b >= m) {
        sum += (b / m) * n;
        b %= m;
    }
    long long y = (a * n + b) / m;
    if (y == 0) return sum;
    long long x = (m * y - b + a - 1) / a;
    sum += (n - x) * y + floor_sum(y, a, m, a * x - m * y + b);
    return sum;
}
#line 4 "test/yosupo/sum_of_floor_of_linear.test.cpp"

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

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

Back to top page