Submit Info #15864

Problem Lang User Status Time Memory
Sum of Floor of Linear cpp AlphaQ AC 66 ms 1.90 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.68 MiB
random_00 AC 17 ms 0.91 MiB
random_01 AC 66 ms 1.90 MiB
random_02 AC 51 ms 1.56 MiB
random_03 AC 35 ms 1.30 MiB
random_04 AC 21 ms 0.90 MiB
small_00 AC 11 ms 0.79 MiB
small_01 AC 37 ms 1.08 MiB
small_02 AC 27 ms 1.01 MiB
small_03 AC 20 ms 0.88 MiB
small_04 AC 9 ms 0.74 MiB

#include <bits/stdc++.h> using namespace std; typedef long long ll; ll sum (ll n) { return n * (n - 1) / 2; } // sum [(a + di) / m] for 0 <= i < n ll floorAPsum (ll a, ll d, ll m, ll n) { ll res = d / m * sum(n) + a / m * n; d %= m, a %= m; if (!d) return res; ll to = (n * d + a) / m; return res + (n - 1) * to - floorAPsum(m - 1 - a, m, d, to); } // sum (a + di) % m for 0 <= i < n ll modAPsum (ll a, ll d, ll m, ll n) { a = ((a % m) + m) % m, d = ((d % m) + m) % m; return n * a + d * sum(n) - m * floorAPsum(a, d, m, n); } int main() { int t; cin >> t; while (t--) { int n, m, a, b; scanf("%d %d %d %d", &n, &m, &a, &b); printf("%lld\n", floorAPsum(b, a, m, n)); } return 0; }