sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#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"; } }