Submit Info #4599

Problem Lang User Status Time Memory
Sum of Floor of Linear cpp KaedeTakagaki AC 87 ms 1.83 MiB

Name Status Time Memory
example_00 AC 1 ms 0.72 MiB
random_00 AC 23 ms 0.92 MiB
random_01 AC 87 ms 1.83 MiB
random_02 AC 68 ms 1.62 MiB
random_03 AC 46 ms 1.30 MiB
random_04 AC 26 ms 0.92 MiB
small_00 AC 13 ms 0.70 MiB
small_01 AC 45 ms 1.10 MiB
small_02 AC 30 ms 0.92 MiB
small_03 AC 21 ms 0.80 MiB
small_04 AC 10 ms 0.67 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 mod 1000000007 #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 t; int main(){ scanf("%d",&t); while(t--){ ll n,m,a,b; scanf("%lld%lld%lld%lld",&n,&m,&a,&b); printf("%lld\n",gs.count(0,n-1,m,a,b)); } }