test/yosupo_sum_of_floor_of_linear.test.cpp

View this file on GitHub
Last update: 2021-06-21 15:24:20+09:00
Problem: https://judge.yosupo.jp/problem/sum_of_floor_of_linear

Depends on

math/floor_sum.cpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/sum_of_floor_of_linear"
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using uint = unsigned;
using ull = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

#include "../math/floor_sum.cpp"

int main() {
    int t;
    cin >> t;
    while(t--) {
        ll n, m, a, b;
        scanf("%lld %lld %lld %lld", &n, &m, &a, &b);
        printf("%lld\n", floor_sum(n, m, a, b));
    }
    return 0;
}

#line 1 "test/yosupo_sum_of_floor_of_linear.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/sum_of_floor_of_linear"
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using uint = unsigned;
using ull = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

#line 1 "math/floor_sum.cpp"
ll floor_sum(ll n, ll m, ll a, ll b){
    ll ans = 0;
    if(a >= m) {
        ans += (n-1)*n/2*(a/m);
        a %= m;
    }
    if (b >= m){
        ans += n*(b/m);
        b %= m;
    }
    ll y = (a*n+b)/m, x = (y*m - b);
    if(!y) return ans;
    ans += (n-(x+a-1)/a)*y;
    ans += floor_sum(y, a, m, (a - x%a)%a);
    return ans;
}
#line 21 "test/yosupo_sum_of_floor_of_linear.test.cpp"

int main() {
    int t;
    cin >> t;
    while(t--) {
        ll n, m, a, b;
        scanf("%lld %lld %lld %lld", &n, &m, &a, &b);
        printf("%lld\n", floor_sum(n, m, a, b));
    }
    return 0;
}