Submit Info #12067

Problem Lang User Status Time Memory
Sum of Floor of Linear cpp Bogdan AC 89 ms 1.86 MiB

ケース詳細
Name Status Time Memory
example_00 AC 3 ms 0.68 MiB
random_00 AC 23 ms 0.99 MiB
random_01 AC 89 ms 1.86 MiB
random_02 AC 68 ms 1.61 MiB
random_03 AC 46 ms 1.30 MiB
random_04 AC 23 ms 0.96 MiB
small_00 AC 13 ms 0.72 MiB
small_01 AC 43 ms 1.02 MiB
small_02 AC 33 ms 0.92 MiB
small_03 AC 22 ms 0.84 MiB
small_04 AC 13 ms 0.73 MiB

#ifdef DEBUG #define _GLIBCXX_DEBUG #endif //#pragma GCC optimize("O3") #include <bits/stdc++.h> using namespace std; typedef long double ld; typedef long long ll; ll solveNaive(ll N, ll M, ll A, ll B) { ll val = 0; for (int i = 0; i < N; i++) { val += (A * i + B) / M; } return val; } ll solve(ll N, ll M, ll A, ll B) { assert(M > 0); if (B < 0) { ll at_least = (-B + M - 1) / M; return solve(N, M, A, B + at_least * M) - N * at_least; } if (A == 0) { return (B / M) * N; } assert(0 <= B && B < M); if (A >= M) { return solve(N, M, A % M, B) + (A / M) * ((N * (N - 1)) / 2); } ll up = (A * (N - 1) + B) / M; ll val = N * up; val -= (B / A); return val - solve(up + 1, A, M, A - 1 - B); } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // freopen("input.txt", "r", stdin); int tst; cin >> tst; while (tst--) { ll N, M, A, B; cin >> N >> M >> A >> B; cout << solve(N, M, A, B) << '\n'; } return 0; }