TopCoder SRM 596 Div2 Hard SparseFactorialDiv2

Div1 Hardの制限を緩めた問題。
http://community.topcoder.com/stat?c=problem_statement&pm=12838

問題

自然数Nについて、関数F(N)を以下のように定める。
F(N)=(N-0^2)*(N-1^2)*(N-2^2)*...*(N-K^2)
ここでKはK^2＜Nとなる最大の非負整数である。

２つの数値L,Hと、素数Dが与えられたとき、F(L)～F(H)のうちDで割り切れる値の数を答えよ。

解法

F(N)を求められれば、答えはF(H)-(F(L)-1)を求めるだけなので、まずはF(N)を求める。
各Kについて、N=(K*K+1)～( (K+1)*(K+1) )の間は、F(N)の計算で最後の項の(N-K^2)のKは同一である。
よって、0～(K^2)においてそれをDで割ったときの値が何になるかを覚えておく。

0～(K^2)でDを割ったときの値がP通りあるなら、1～Nまでの間でDで割れるのはおおよそN/D*Pであることを使って、(K*K+1)～( (K+1)*(K+1) )の間にあるF(N)がDで割り切れる要素数をO(D)で計算できる。

Kの最大値は高々√Hであることから、全体の計算量はO(D√H)であるが、これだとまだTLEする。
Kを１つずつ加算して(K*K+1)～( (K+1)*(K+1) )中の値を計算するのではなく、(K^2)%Dがすでに登場済みの値だった場合はそのKをスキップすることで高速化することができる。

class SparseFactorialDiv2 {
	public:
	ll func(ll val,ll div) {
		int rem[1000],nr=0;
		ll ret=0;
		ZERO(rem);
		
		for(ll k=0;k*k<=val;k++) {
			ll lo=k*k;
			retry:
			ll hi=min((k+1)*(k+1),val);
			
			ll tr=(k*k)%div;
			if(rem[tr]) {
				if((k+1)*(k+1)<=val) {
					k++;
					goto retry;
				}
			}
			else rem[tr]++,nr++;
			
			while(lo%div) ret-=rem[lo%div],lo--;
			while(hi%div) ret+=rem[hi%div],hi--;
			ret += (hi-lo)/div*nr;
		}
		return ret;
	}
	
	long long getCount(long long lo, long long hi, long long divisor) {
		return func(hi,divisor)-func(lo-1,divisor);
	}
};

まとめ

そこまで実装も重くなくてよい問題。