test/math/FloorSum.test.cpp

View this file on GitHub
Last update: 2023-05-30 04:49:31+09:00
Problem: https://judge.yosupo.jp/problem/sum_of_floor_of_linear

Depends on

FloorSum - 直線領域の格子点数 (lib/30-math/FloorSum.cpp)

Code

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

#include <iostream>
using namespace std;
#include "../../lib/30-math/FloorSum.cpp"

int main() {
    cin.tie(nullptr);ios::sync_with_stdio(false);
    int Q; cin >> Q;
    while(Q--){
        long long N,M,A,B; cin >> N >> M >> A >> B;
        cout << FloorSum(N,M,A,B) << "\n";
    }
    return 0;
}

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

#include <iostream>
using namespace std;
#line 1 "lib/30-math/FloorSum.cpp"
/**
 * @title FloorSum - 直線領域の格子点数
 * @docs md/math/FloorSum.md
 */
inline static long long FloorSum(long long n, long long m, long long a, long long b) {
    long long ret=0;
    while(1) {
        if(a >= m) ret += ((n-1)*n*(a/m))>>1,a%=m;
        if(b >= m) ret += n*(b / m),b%=m;
        long long y=(a*n+b)/m, x=(y*m-b);
        if(y==0) return ret;
        ret += (n-(x+a-1)/a)*y;
        b=(a-x%a)%a; swap(a,m); n=y;
    }
}
#line 6 "test/math/FloorSum.test.cpp"

int main() {
    cin.tie(nullptr);ios::sync_with_stdio(false);
    int Q; cin >> Q;
    while(Q--){
        long long N,M,A,B; cin >> N >> M >> A >> B;
        cout << FloorSum(N,M,A,B) << "\n";
    }
    return 0;
}