Submit Info #11452

Problem Lang User Status Time Memory
Sum of Floor of Linear cpp YouKn0wWho AC 71 ms 1.85 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.67 MiB
random_00 AC 18 ms 0.92 MiB
random_01 AC 71 ms 1.85 MiB
random_02 AC 50 ms 1.61 MiB
random_03 AC 37 ms 1.30 MiB
random_04 AC 18 ms 0.92 MiB
small_00 AC 11 ms 0.72 MiB
small_01 AC 35 ms 1.05 MiB
small_02 AC 29 ms 0.93 MiB
small_03 AC 20 ms 0.84 MiB
small_04 AC 10 ms 0.80 MiB

#include<bits/stdc++.h> using namespace std; const int N = 3e5 + 9; /* Sums of arithmetic progressions. mod_sum(n, a, d, m) = \sum_{i = 0}^{n - 1}{(a + d * i) % m}. floor_sum(n, a, d, m) = \sum_{i = 0}^{n - 1}{(a + d * i) / m}. log(m), with a large constant. */ long long sumsq(long long n) { return n / 2 * ((n - 1) | 1); } long long floor_sum(long long a, long long d, long long m, long long n) { long long res = d / m * sumsq(n) + a / m * n; d %= m; a %= m; if (!d) return res; long long to = (n * d + a) / m; return res + (n - 1) * to - floor_sum(m - 1 - a, m, d, to); } long long mod_sum(long long a, long long d, long long m, long long n) { a = ((a % m) + m) % m; d = ((d % m) + m) % m; return n * a + d * sumsq(n) - m * floor_sum(a, d, m, n); } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while (t--) { int n, m, a, b; cin >> n >> m >> a >> b; cout << floor_sum(b, a, m, n) << '\n'; } return 0; }