Submit Info #10536

Problem Lang User Status Time Memory
Sum of Floor of Linear cpp yhchang3 AC 90 ms 1.66 MiB

Name Status Time Memory
example_00 AC 3 ms 0.72 MiB
random_00 AC 23 ms 0.99 MiB
random_01 AC 90 ms 1.66 MiB
random_02 AC 67 ms 1.64 MiB
random_03 AC 50 ms 1.23 MiB
random_04 AC 19 ms 0.92 MiB
small_00 AC 10 ms 0.80 MiB
small_01 AC 38 ms 1.12 MiB
small_02 AC 30 ms 1.00 MiB
small_03 AC 22 ms 0.87 MiB
small_04 AC 9 ms 0.68 MiB

#include<bits/stdc++.h> using namespace std; typedef long long int ll; struct Data{ll f,g,h;};//n should be non-negative //f=\sum_{i=0}^n((ai+b)/c),g=\sum_{i=0}^n(i((ai+b)/c)) //h=\sum_{i=0}^n((ai+b)/c)^2,(i2,i6)->(/2,/6) Data solve(ll n,ll a,ll b,ll c){ Data d,e;ll ac=a/c,bc=b/c,m=(a*n+b)/c,n1=n+1,n21=n*2+1; if(a>=c||b>=c){ e=solve(n,a%c,b%c,c); d.f=n1*n/2*ac+bc*n1+e.f,d.g=ac*n*n1*n21/6+bc*n*n1/2+e.g; d.h=ac*ac*n*n1*n21/6+bc*bc*n1+ac*bc*n*n1+e.h+bc*2*e.f+ac*2*e.g; return d; } if(a==0||n<0) return d.f=d.g=d.h=0,d; e=solve((a*n+b)/c-1,c,c-b-1,a); d.f=m*n-e.f,d.g=(m*n*n1-e.h-e.f),d.h=m*n*(m+1)-e.g*2-e.f*2-d.f; return d; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int T; cin>>T; while(T--){ ll n,m,a,b; cin>>n>>m>>a>>b; cout<<solve(n-1,a,b,m).f<<'\n'; } }