yukicoder : No.2645 Sum of Divisors?

また知らないテクが出てきた。
https://yukicoder.me/problems/no/2645

問題

整数nの約数の個数をd(n)とする。
正整数Nが指定されるので、を求めよ。

解法

約数として、ある数sが、どれだけ解に寄与するかを考えると

f(n) := 1/1 + 1/2 + ....とすると、右辺はf(N/s)/sとなる。
N/sのバリエーションはO(√N)程度しかないので、それらをまとめて計算しよう。
あとは大きなnに対するf(n)を求める必要がある。
ある程度大きなkまでは愚直にf(k)を計算し、それ以上は[\tex \displaystyle f(n) \simeq f(k) + log(n)-log(k)]で近似すると良い。

const ll DI=1000000;
double Hs[1010101];

ll N;

double H(ll v) {
	if(Hs[1]==0) {
		for(int i=1;i<=DI;i++) Hs[i]=Hs[i-1]+1.0/i;
	}
	if(v<=DI) return Hs[v];
	return Hs[DI]+log(v)-log(DI);
	
	
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	double ret=0;
	ll cur=N;
	while(cur>0) {
		ll a=N/cur;
		ll nex=N/(a+1);
		ret+=H(a)*(H(cur)-H(nex));
		cur=nex;
	}
	_P("%.12lf\n",ret);
}

まとめ

この近似テク思いつかなかったな。