#include using namespace std; #pragma GCC optimize ("O3") #pragma GCC target ("avx2") #pragma GCC optimize("unroll-loops") unsigned long long floor_sum(unsigned long long N,unsigned long long M,unsigned long long A,unsigned long long B) //Sum[floor((A*i+B)/M),{i,0,N-1}] { unsigned long long ans=0; if(A>=M) { unsigned long long AM=A/M; ans+=N*(N-1)/2*AM; A-=AM*M; } if(B>=M) { unsigned long long BM=B/M; ans+=N*BM; B-=BM*M; } unsigned long long Ym=(A*N+B)/M,Xm=Ym*M-B; if(Ym==0)return ans; unsigned long long TX=(Xm+A-1)/A; ans+=(N-TX)*Ym; ans+=floor_sum(Ym,A,M,TX*A-Xm); return ans; } int N,M; int A[2000],B[2000]; main() { scanf("%d%d",&N,&M); for(int i=0;i