kmjp's blog

競技プログラミング参加記です

yukicoder : No.752 mod数列

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;
	}
}

まとめ

似た問題見たことあるはずなので手こずった。