kmjp's blog

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

yukicoder : No.1180 無限和

yukicoder

こういう式変形さらっとできないなぁ。
https://yukicoder.me/problems/no/1180

問題

整数Nが与えられる。
\displaystyle \sum_{a_1=1}^\infty \sum_{a_2=1}^\infty ..... \sum_{a_N=1}^\infty \frac{1}{{a_1}^2 B}の整数部分を求めよ。
ここで、 \displaystyle A = \prod_{k=1}^n {a_k}^2 , B = \sum_{k=1}^n \frac{A}{{a_k}^2}とする。

解法

サンプルにあるN=1の時に解がπ^2/6となるのがヒントになっている。
与えられた式はa_1以外対称なので、Bにかかるa_1^2の部分をa_2～a_Nに差し替えても解が等しい。
そこで、差し替えたものの平均を取れば解が一致するはずである。

よって解は \displaystyle \frac{1}{N} \times \sum_{a_1=1}^\infty \sum_{a_2=1}^\infty \cdots \sum_{a_N=1}^\infty (\frac{1}{{a_1}^2B}+\frac{1}{{a_2}^2B}+ \cdots +\frac{1}{{a_N}^2B})
\displaystyle = \frac{1}{N} \times \sum_{a_1=1}^\infty \frac{1}{{a_1}^2} \times \sum_{a_2=1}^\infty \frac{1}{{a_2}^2} \times \cdots \times \sum_{a_n=1}^\infty \frac{1}{{a_N}^2} = \frac{\pi ^ {2N}}{N6^N}

int N;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	double a=atan(1)*4;
	a=a*a/6;
	
	double ret=pow(a,N)/N;
	
	cout<<(ll)floor(ret)<<endl;
}

まとめ

こういう式変形メインで実装は簡単な問題、AtCoderにもCodeforcesにも少ないしyukicoderらしさを感じるね。