Submit Info #147

Problem Lang User Status Time Memory
Sum of Floor of Linear cpp yosupo AC 96 ms 1.93 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.68 MiB
random_00 AC 24 ms 0.92 MiB
random_01 AC 96 ms 1.93 MiB
random_02 AC 72 ms 1.54 MiB
random_03 AC 52 ms 1.30 MiB
random_04 AC 23 ms 0.92 MiB
small_00 AC 12 ms 0.80 MiB
small_01 AC 44 ms 1.02 MiB
small_02 AC 35 ms 0.92 MiB
small_03 AC 23 ms 0.80 MiB
small_04 AC 0 ms 0.73 MiB

#include <iostream> #include <vector> #include <algorithm> using namespace std; using uint = unsigned int; using ll = long long; using ull = unsigned long long; constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); } template <class T> using V = vector<T>; template <class T> using VV = V<V<T>>; /** * a / b, a // b : 小数, 整数としての割り算 * sum_{i = 0..n-1} (ai + b) // m を求める * * 線分 y = (ax + b) / m, (0 <= x <= n)は真下に何個(完全な)正方形を含むか?と同値 */ ll sum_of_floor(ll n, ll m, ll a, ll b) { ll ans = 0; if (a >= m) { ans += (n - 1) * n * (a / m) / 2; a %= m; } if (b >= m) { ans += n * (b / m); b %= m; } /** * 線分の端点を、y座標が整数になるようにちょっとずらす -> 90度回転 * y座標: (b / m, (an + b) / m) -> (0, y_max) * x座標: (0, n) -> (-b / a, x_max / a) * * 端点をずらすことで答えは (n - ceil(x_max / a)) * y_max 減る * * 90度回転する * (m / a) * x + (b2 / a) = y_max */ ll y_max = (a * n + b) / m, x_max = (y_max * m - b); if (y_max == 0) return ans; ans += (n - (x_max + a - 1) / a) * y_max; ans += sum_of_floor(y_max, a, m, (a - x_max % a) % a); return ans; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int t; cin >> t; for (int i = 0; i < t; i++) { ll n, m, a, b; cin >> n >> m >> a >> b; cout << sum_of_floor(n, m, a, b) << "\n"; } return 0; }