Submit Info #7028

Problem Lang User Status Time Memory
Sum of Floor of Linear cpp satashun AC 69 ms 1.83 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.67 MiB
random_00 AC 17 ms 0.92 MiB
random_01 AC 69 ms 1.83 MiB
random_02 AC 53 ms 1.58 MiB
random_03 AC 34 ms 1.21 MiB
random_04 AC 18 ms 0.95 MiB
small_00 AC 10 ms 0.69 MiB
small_01 AC 37 ms 1.03 MiB
small_02 AC 29 ms 0.95 MiB
small_03 AC 20 ms 0.86 MiB
small_04 AC 12 ms 0.72 MiB

#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int, int>; template<class T> using V = vector<T>; template<class T> using VV = V<V<T>>; #define pb push_back #define eb emplace_back #define mp make_pair #define fi first #define se second #define rep(i,n) rep2(i,0,n) #define rep2(i,m,n) for(int i=m;i<(n);i++) #define ALL(c) (c).begin(),(c).end() #ifdef LOCAL #define dump(x) cerr << __LINE__ << " " << #x << " = " << (x) << endl #else #define dump(x) true #endif constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); } template<class T, class U> void chmin(T& t, const U& u) { if (t > u) t = u; } template<class T, class U> void chmax(T& t, const U& u) { if (t < u) t = u; } template<class T, class U> ostream& operator<<(ostream& os, const pair<T, U>& p) { os<<"("<<p.first<<","<<p.second<<")"; return os; } template<class T> ostream& operator<<(ostream& os, const vector<T>& v) { os<<"{"; rep(i, v.size()) { if (i) os<<","; os<<v[i]; } os<<"}"; return os; } //x_i=floor((a*i+b)/c), i=0,1,..n-1 //a,c>0, b>=0 //http://mathforum.org/library/drmath/view/73120.html //https://min-25.hatenablog.com/entry/2018/04/27/225535 ll gauss_sum(ll n, ll a, ll b, ll c) { if (n == 0) return 0; ll res = 0; { ll p = a / c; res += n * (n-1) / 2 * p; a %= c; } { ll p = b / c; res += n * p; b %= c; } if (a == 0) return res; ll top = (a * (n-1) + b) / c; res += top * n; ll h = 1; if (h <= top) { res -= gauss_sum(top - h + 1, c, c * h - (b + 1), a) + top - h + 1; } return res; } int main() { int T; scanf("%d", &T); while (T--) { int n,m,a,b; scanf("%d %d %d %d", &n, &m, &a, &b); ll ans = gauss_sum(n, a, b, m); printf("%lld\n", ans); } return 0; }