GよりFに苦戦…。
https://atcoder.jp/contests/abc443/tasks/abc443_g
問題
正整数N,M,A,Bが与えられる。
N要素の整数列Xを、X[k] = (Ak+B) % M としたとき、X[k]>kとなるkはいくつか。
解法
X[k]>kであるには、floor((Ak+B)/M)+1= floor((Ak+B+M-k-1)/M)であればよい。
そこでfloor_sum(N,M,A-1,M+B-1)-floor_sum(N,M,A,B)を答えればよい。
int T; ll N,M,A,B; template<class V> V floor_sum(V N,V M,V A,V B) { // sum(i=0...N-1) floor((A*i+B)/M) if(A<0) return floor_sum(N,M,-A,B+(N-1)*A); //Aが負の場合傾きを逆にする V ret=0; if(B>=M) ret+=N*(B/M), B%=M; if(A>=M) ret+=N*(N-1)/2*(A/M), A%=M; V Y=(A*N+B)/M; if(Y==0) return ret; //floor(Y/M)に達するX V X=Y*M-B; //Xの右側はY個ずつ ret+=(N-(X+A-1)/A)*Y; // 90度回転、Y=Nのラインは無視する ret+=floor_sum(Y,A,M,(A-X%A)%A); return ret; } void solve() { int i,j,k,l,r,x,y; string s; cin>>T; while(T--) { cin>>N>>M>>A>>B; ll le=floor_sum<__int128>(N,M,A,B); ll ok=floor_sum<__int128>(N,M,A-1,M+B-1); cout<<ok-le<<endl; } }
まとめ
いかにもfloor_sum使えって感じの問題。