yukicoder No.454 逆2乗和

yukicoder

問題URL : http://yukicoder.me/problems/no/454

問題概要

非負実数xが与えられる．
{ \displaystyle \sum_{n=1}^{\infty} \frac{1}{(n+x)^2} }を計算せよ．

{ \displaystyle 0 \leq x \leq 1000 }

解法

厳密解を求めるのは難しいので近似解を求める．
xの整数部分をa，小数部分をbとする．
問題文に書かれている公式{ \displaystyle \sum_{n=1}^{\infty} \frac{1}{n^2} = \frac{\pi^2}{6} }を用いて計算式を変形すると

{ \displaystyle \begin{eqnarray} \sum_{n=1}^{\infty} \frac{1}{(n+x)^2} &=& \sum_{n=1}^{\infty} \frac{1}{(n+a+b)^2} \\ &=& \sum_{n=a+1}^{\infty} \frac{1}{(n+b)^2} \\ &=& \sum_{n=a+1}^{\infty} \frac{1}{(n+b)^2} \\ &\fallingdotseq& \sum_{n=a+1}^{N} \frac{1}{(n+b)^2} + \sum_{n=N+1}^{\infty} \frac{1}{n^2} \\ &=& \sum_{n=a+1}^{N} \frac{1}{(n+b)^2} + \sum_{n=1}^{\infty} \frac{1}{n^2} - \sum_{n=1}^{N} \frac{1}{n^2} \\ &=& \sum_{n=a+1}^{N} \frac{1}{(n+b)^2} + \frac{\pi^2}{6} - \sum_{n=1}^{N} \frac{1}{n^2} \\ \end{eqnarray} }
となる．
あとは {\displaystyle N}をどれくらい大きくすれば許容誤差に収まるかを考ればよい．
{ \displaystyle \frac{1}{n^2} - \frac{1}{(n+b)^2} \leq \frac{1}{n^2} - \frac{1}{(n+1)^2} = O(\frac{1}{n^2}) }なので
{\displaystyle N = 10^5}とすれば誤差は {\displaystyle 10^{-9}}以下となる（気がする）．

コード

void mainmain() {
	double x;
	cin >> x;
	int a = x;
	double b = x - a;
	double sum1 = 0;
	double sum2 = 0;
	int N = 1e5;
	reep(i, 1 + a, N) {
		sum1 += pow(1. / (i + b), 2);
	}
	reep(i, 1, N) {
		sum2 += pow(1. / i, 2);
	}
	double ans = sum1 + pow(acos(-1), 2) / 6 - sum2;
	cout << ans << endl;
}

コメント

解説を見たら想定別解と方針は似てました．（想定別解はおそらく間違いが含まれている）