Submit Info #1130

Problem Lang User Status Time Memory
Sum of Floor of Linear cpp (anonymous) AC 178 ms 1.80 MiB

Name Status Time Memory
example_00 AC 2 ms 0.72 MiB
random_00 AC 50 ms 0.92 MiB
random_01 AC 178 ms 1.80 MiB
random_02 AC 138 ms 1.61 MiB
random_03 AC 93 ms 1.20 MiB
random_04 AC 39 ms 0.95 MiB
small_00 AC 29 ms 0.68 MiB
small_01 AC 101 ms 1.08 MiB
small_02 AC 78 ms 0.92 MiB
small_03 AC 57 ms 0.84 MiB
small_04 AC 27 ms 0.70 MiB

#pragma GCC optimize("Ofast") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; typedef long long ll; typedef pair<int,int> P; typedef pair<int,P> P1; typedef pair<P,P> P2; #define pu push #define pb push_back #define mp make_pair #define eps 1e-7 #define INF 1000000000 #define fi first #define sc second #define rep(i,x) for(int i=0;i<x;i++) #define repn(i,x) for(int i=1;i<=x;i++) #define SORT(x) sort(x.begin(),x.end()) #define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end()) #define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) #define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) struct gausssum{ ll md(ll x,ll y){ if(x>=0) return x/y; ll vl=md(-x,y); if((-x)%y==0) return -vl; else return -vl-1; } //[(ax+b)/n] (s<=x<=t) ll count(ll s,ll t,ll n,ll a,ll b){ if(a < 0){ return count(-t,-s,n,-a,b); } ll S = md(a*s+b,n), T = md(a*t+b,n); if(S == T) return (t-s+1)*S; if(n <= a){ ll sum = (s+t)*(t-s+1)/2LL; return count(s,t,n,a%n,b)+sum*(a/n); } ll sum = count(S+1,T,a,n,-b-1); ll all = T*t-S*(s-1); return all-sum; } }gs; int main(){ int t; scanf("%d",&t); rep(i,t){ ll n,m,a,b; cin >> n >> m >> a >> b; cout << gs.count(0,n-1,m,a,b) << endl; } }