Submit Info #15863

Problem Lang User Status Time Memory
Sum of Floor of Linear cpp AlphaQ AC 78 ms 1.89 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.72 MiB
random_00 AC 22 ms 0.92 MiB
random_01 AC 78 ms 1.89 MiB
random_02 AC 63 ms 1.57 MiB
random_03 AC 42 ms 1.24 MiB
random_04 AC 23 ms 0.91 MiB
small_00 AC 15 ms 0.68 MiB
small_01 AC 40 ms 1.03 MiB
small_02 AC 31 ms 0.92 MiB
small_03 AC 23 ms 0.80 MiB
small_04 AC 12 ms 0.73 MiB

#include <bits/stdc++.h> using namespace std; typedef long long ll; // sum [(x + kn) / m] for 0 <= k < m inline ll aux (ll x, ll n, ll m) { ll g = __gcd(n, m); return g * (x / g) + (m * n - m - n + g) / 2; } // sum [(x + kn) / m] for 0 <= k < lim < m ll get (ll x, ll n, ll m, ll lim) { if (!lim) return 0; ll ret = lim * (x / m) + lim * (lim - 1) * (n / m) / 2; n %= m, x %= m; if (!n) return ret; ll p = (x + (lim - 1) * n) / m; return ret + p * lim - get(m - x + n - 1, m, n, p); } // sum [(x + kn) / m] for 0 <= k < lim in O(lg max(n, m)) // m > 0, lim >= 0 inline ll floorAPsum (ll x, ll n, ll m, ll lim) { ll ret = 0; if (x < 0) { ll q = x / m; x %= m; if (x) x += m, --q; ret += q * lim; } if (n < 0) { ll q = n / m; n %= m; if (n) n += m, --q; ret += lim * (lim - 1) * q / 2; } ll tmp = aux(x, n, m), tot = lim / m; ret += tmp * tot + tot * (tot - 1) * n * m / 2 + tot * n * (lim - tot * m); return ret + get(x, n, m, lim % m); } ll brute (ll x, ll n, ll m, ll lim) { ll ret = 0; for (ll k = 0; k < lim; ++k) { if ((x + k * n) % m == 0) ret += (x + k * n) / m; else if (x + k * n < 0) ret += (x + k * n) / m - 1; else ret += (x + k * n) / m; } return ret; } int main() { int t; cin >> t; while (t--) { int x, n, m, lim; scanf("%d %d %d %d", &lim, &m, &n, &x); printf("%lld\n", floorAPsum(x, n, m, lim)); } return 0; }