Submit Info #4041

Problem Lang User Status Time Memory
Sum of Floor of Linear cpp TKO919 AC 92 ms 1.82 MiB

Name Status Time Memory
example_00 AC 1 ms 0.72 MiB
random_00 AC 24 ms 0.95 MiB
random_01 AC 92 ms 1.82 MiB
random_02 AC 69 ms 1.56 MiB
random_03 AC 50 ms 1.30 MiB
random_04 AC 21 ms 0.92 MiB
small_00 AC 14 ms 0.73 MiB
small_01 AC 45 ms 1.00 MiB
small_02 AC 34 ms 0.91 MiB
small_03 AC 24 ms 0.80 MiB
small_04 AC 10 ms 0.68 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; }