TopCoder SRM 529 Div1 Medium MinskyMystery

Div2Hardの改変問題。
http://community.topcoder.com/stat?c=problem_statement&pm=11739

問題

基本的な問題設定はDiv2 Hardと同じ。
TopCoder SRM 529 Div2 Hard MinskyMysteryDiv2 - kmjp's blog

Div2 Hardでは4番目の袋の石の数を答えるが、こちらは袋に追加した石の数と袋の間で石を動かした回数の和を答える。

解法

開始時の石の数をNとする。
Div2同様、(1番目の袋の石の数)=2から初めて(1番目の袋の石の数)がNで割れるまで1番目の袋の石をインクリメントしつつループを繰り返す。

Nにおける2以上の最初の約数をDとすると、答えは $(4*N+2)*(D-1)-N+\sum^{D}_{i=2} \lceil \frac{N}{i} \rceil$ である。

N ≤ 10^12なので、最初の約数DはO(√N)で見つかる。
残る問題は $\sum^{D}_{i=2} \lceil \frac{N}{i} \rceil$ の部分で、Nが素数の場合、N=Dとなるので愚直に計算するとO(N)かかりTLEする。

よってこの部分の処理を高速化することを考える。
まずi=2～√Nまでは普通にN/iを計算する。

残り√N+1～Nの部分だが、これもO(√N)で計算できる。
例えば、N/iが1となるのはi=(N/2+1)～Nの間で、N/i=2となるのはi=N/3+1～N/2、とN/iが一致する複数のiの分をまとめて足しこむことができる。

ll mo=1000000009;

class MinskyMystery {
	public:
	int computeAnswer(long long N) {
		ll i;
		ll div;
		if(N<=1) return -1;
		
		for(div=2;div*div<=N;div++) if(N%div==0) break;
		if(N%div) div=N;
		
		ll ret=((4*N+2)%mo*((div-1)%mo))%mo;
		
		if(div<N) {
			for(i=2;i<=div;i++) ret+=(N/i);
		}
		else {
			ll ma=0;
			for(i=1;i*i<N;i++) {
				ll num=N/i - N/(i+1);
				ret=(ret+num*i)%mo;
				ma=N/(i+1);
			}
			for(i=2;i<=ma;i++) ret=(ret+(N/i))%mo;
			
		}
		ret -= N;
		return (int) ((mo+(ret%mo))%mo);
	}
}

まとめ

Div2 Hardでも思ったけど、いまいち何がしたいかわからない問題。