Submit Info #2199

Problem Lang User Status Time Memory
Sum of Floor of Linear cpp (anonymous) AC 180 ms 1.79 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.72 MiB
random_00 AC 50 ms 0.99 MiB
random_01 AC 180 ms 1.79 MiB
random_02 AC 138 ms 1.55 MiB
random_03 AC 98 ms 1.23 MiB
random_04 AC 44 ms 0.92 MiB
small_00 AC 29 ms 0.72 MiB
small_01 AC 105 ms 1.00 MiB
small_02 AC 78 ms 0.92 MiB
small_03 AC 58 ms 0.82 MiB
small_04 AC 25 ms 0.67 MiB

#include<bits/stdc++.h> using namespace std; typedef long long ll; 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; } 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(){ int t; cin >> t; while(t--){ ll n,m,a,b; cin >> n >> m >> a >> b; cout << sum_of_floor(n,m,a,b) << endl; } }