Codeforcesで見たような気もするけど違うかな。
https://yukicoder.me/problems/no/752
問題
整数Pに対し、A[i]=P mod iと定義する。
以下のクエリにそれぞれ答えよ。
- 区間[L,R]が与えられる。sum(A[L...R])を答えよ。
解法
A[i] = P mod i = P - i*floor(P/i)
である。よって、P/iが同じであるようなiについて、A[i]の区間和はO(1)で求められる。
P/iの変動が大きい、A[1]~A[1000000]程度までは先に求めておき、累積和を求めよう。
A[1000001]以降は上記の要領でP/iが等しいものをまとめて和を取ればよい。
解説ではP/iが等しい物同士の和に対しさらに累積和を取っているが、そこまでしなくても通る。
int P,Q; int L,R; ll A[1010100],S[1010100]; int nex[1010100]; void solve() { int i,j,k,l,r,x,y; string s; cin>>P>>Q; nex[0]=P+1; for(i=1;i<=1000001;i++) { A[i]=P%i; S[i]=S[i-1]+A[i]; nex[i]=P/(i+1)+1; } while(Q--) { cin>>L>>R; ll ret=0; if(R<=1000000) { ret=S[R]-S[L-1]; } else { if(L<=1000000) { ret+=S[1000000]-S[L-1]; L=1000001; } x=P/L; y=P/R; while(x!=y) { int ne=nex[x-1]-1; ret+=1LL*P*(ne-L+1)-1LL*x*(ne+L)*(ne-L+1)/2; x--; L=nex[x]; } ret+=1LL*P*(R-L+1)-1LL*y*(R+L)*(R-L+1)/2; } cout<<ret<<endl; } }
まとめ
似た問題見たことあるはずなので手こずった。