Submit Info #3970

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

Name Status Time Memory
example_00 AC 3 ms 0.68 MiB
random_00 AC 23 ms 0.92 MiB
random_01 AC 83 ms 1.80 MiB
random_02 AC 73 ms 1.52 MiB
random_03 AC 51 ms 1.25 MiB
random_04 AC 23 ms 0.92 MiB
small_00 AC 12 ms 0.67 MiB
small_01 AC 42 ms 1.05 MiB
small_02 AC 35 ms 0.97 MiB
small_03 AC 24 ms 0.82 MiB
small_04 AC 12 ms 0.70 MiB

#define _USE_MATH_DEFINES #include <bits/stdc++.h> using namespace std; //template #define rep(i,a,b) for(int i=(a);i<(b);i++) #define rrep(i,a,b) for(int i=(a);i>(b);i--) #define ALL(v) (v).begin(),(v).end() typedef long long int ll; const int inf = 0x3fffffff; const ll INF = 0x1fffffffffffffff; const double eps=1e-12; void tostr(ll x,string& res){while(x)res+=('0'+(x%10)),x/=10; reverse(ALL(res)); return;} template<class T> inline bool chmax(T& a,T b){ if(a<b){a=b;return 1;}return 0; } template<class T> inline bool chmin(T& a,T b){ if(a>b){a=b;return 1;}return 0; } //template end ll calc(ll n,ll m,ll a,ll b){ ll res=0; if(a>=m){res+=(n-1)*n*(a/m)/2; a%=m;} if(b>=m){res+=n*(b/m); b%=m;} ll y=(a*n+b)/m,x=y*m-b; if(y==0)return res; res+=(n-(x+a-1)/a)*y+calc(y,a,m,(a-x%a)%a); return res; } int main(){ int t; scanf("%d",&t); rep(rot,0,t){ ll n,m,a,b; scanf("%lld%lld%lld%lld",&n,&m,&a,&b); printf("%lld\n",calc(n,m,a,b)); } return 0; }