kmjp's blog

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

Codeforces ECR #005 : E. Sum of Remainders

シンプルな問題。
http://codeforces.com/contest/616/problem/E

問題

正整数N,Mが与えられる。
 \displaystyle (\sum_{1\le i \le M} (N\% i)) \% (10^9+7) を答えよ。

解法

平方分割の要領で考える。
iが10^6の範囲は、愚直にN%iを計算して足しこんでいこう。

N = k*i+r (kが商, rが余り)とする。iがある程度大きくなると、あるiの区間でkが等しくなる。
Nをiで割った余りがkとなるiの区間を[L,R]とする。
求めたいのは上記rだが、これはN-k*iで計算できる。
kが同一となるi∈[L,R]に対してこの和は、 \displaystyle \sum_{L\le i \le R} (N-k*i) = (R-L+1)N - k*sum(L...R)で計算できる。
あとはkを0からN/(10^6)程度までループさせならが上記和を足しこんでいこう。

ll N,M;
ll mo=1000000007;
ll rev2 = (mo+1)/2;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	
	ll ret=0;
	ll g;
	for(g=1;g<=min(5000000LL,M);g++) {
		ret+=N%g;
		if(ret>=mo) ret-=mo;
	}
	if(M>5000000) {
		for(ll x=0;;x++) {
			ll L=max(N/(x+1)+1,g);
			ll R=min(M,(x?N/x:M));
			if(R<g) break;
			if(L>R) continue;
			ll a=(N%mo)*((R-L+1)%mo)%mo;
			ll b=x*((L+R)%mo)%mo*((R-L+1)%mo)%mo*rev2%mo;
			ret+=mo+a-b;
			while(ret>=mo) ret-=mo;
		}
	}
	
	cout<<ret<<endl;
	
}

まとめ

妙にバグ仕込んで辛かった。