Submit Info #12112

Problem Lang User Status Time Memory
Sum of Floor of Linear cpp koosaga AC 67 ms 1.79 MiB

ケース詳細
Name Status Time Memory
example_00 AC 3 ms 0.72 MiB
random_00 AC 18 ms 0.95 MiB
random_01 AC 67 ms 1.79 MiB
random_02 AC 51 ms 1.55 MiB
random_03 AC 34 ms 1.20 MiB
random_04 AC 17 ms 0.92 MiB
small_00 AC 10 ms 0.72 MiB
small_01 AC 31 ms 1.05 MiB
small_02 AC 25 ms 0.95 MiB
small_03 AC 22 ms 0.84 MiB
small_04 AC 13 ms 0.68 MiB

#include <bits/stdc++.h> #define sz(v) ((int)(v).size()) #define all(v) (v).begin(), (v).end() using namespace std; using lint = long long; // number of (x, y) : (0 <= x < n && 0 < y <= k/d x + b/d) // argument should be positive lint count_solve(lint n, lint k, lint b, lint d) { if (k == 0) { return (b / d) * n; } if (k >= d || b >= d) { return ((k / d) * (n - 1) + 2 * (b / d)) * n / 2 + count_solve(n, k % d, b % d, d); } return count_solve((k * n + b) / d, d, (k * n + b) % d, k); } int main() { int t; scanf("%d", &t); while (t--) { lint n, m, a, b; scanf("%lld %lld %lld %lld", &n, &m, &a, &b); printf("%lld\n", count_solve(n, a, b, m)); } }