Submit Info #960

Problem Lang User Status Time Memory
Sum of Floor of Linear cpp maroonrk AC 80 ms 1.90 MiB

Name Status Time Memory
example_00 AC 2 ms 0.72 MiB
random_00 AC 20 ms 0.92 MiB
random_01 AC 80 ms 1.90 MiB
random_02 AC 62 ms 1.59 MiB
random_03 AC 44 ms 1.32 MiB
random_04 AC 21 ms 0.98 MiB
small_00 AC 10 ms 0.72 MiB
small_01 AC 40 ms 1.05 MiB
small_02 AC 28 ms 0.92 MiB
small_03 AC 22 ms 0.80 MiB
small_04 AC 9 ms 0.80 MiB

#include <bits/stdc++.h> using namespace std; using ll=long long; #define int ll #define rng(i,a,b) for(int i=int(a);i<int(b);i++) #define rep(i,b) rng(i,0,b) #define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--) #define per(i,b) gnr(i,0,b) #define pb push_back #define eb emplace_back #define a first #define b second #define bg begin() #define ed end() #define all(x),x.ed #ifdef LOCAL #define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl #else #define dmp(x) void(0) #endif template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;} template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;} template<class t> using vc=vector<t>; template<class t> using vvc=vc<vc<t>>; using pi=pair<int,int>; using vi=vc<int>; template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p){ return os<<"{"<<p.a<<","<<p.b<<"}"; } template<class t> ostream& operator<<(ostream& os,const vc<t>& v){ os<<"{"; for(auto e:v)os<<e<<","; return os<<"}"; } //CF530E,ARC055D //x_i=floor((a*i+b)/c), i=0,1,..n-1 //a,c>0, b>=0 int gauss_sum(int n,int a,int b,int c){ if(n==0)return 0; int res=0; { int p=a/c; res+=n*(n-1)/2*p; a%=c; } { int p=b/c; res+=n*p; b%=c; } if(a==0)return res; int top=(a*(n-1)+b)/c; res+=top*n; int h=(b+1+c-1)/c; if(h<=top) res-=gauss_sum(top-h+1,c,c*h-(b+1),a)+top-h+1; return res; } signed main(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20); int t;cin>>t; rep(_,t){ int n,m,a,b;cin>>n>>m>>a>>b; cout<<gauss_sum(n,a,b,m)<<"\n"; } }