109. 冪乗和
【問題概要】
自然数a,b,kが与えられる。a^i+b^i (1 ≦ i ≦ k) の和を求めよ。
【解説】
冪乗和の式に注目すると、i=1からi=kまでのa^i+b^iの和を求めることが目的となる。
このとき、iを固定したときのa^i+b^iは累乗の和の形になっているため、この和を求めることができれば、iを変化させた場合の総和を求めることができる。
累乗の和は、等比級数の和の公式を用いることで求めることができるため、a^i+b^iの総和は等比級数の和の公式を用いて求めることができる。
【問題概要】
整数x, yが与えられる。x^k + y^k (k=1,2,3,...)の和を求めよ。
【解説】
この問題は、k=1,2,3,...という無限級数を扱う問題である。
まず、k=1のとき、x^1 + y^1 = x + yが成り立つ。
k=2のとき、x^2 + y^2 = (x+y)^2 - 2xyが成り立つ。
k=3のとき、x^3 + y^3 = (x+y)(x^2-xy+y^2)が成り立つ。
このように、kの値が増えるにつれて、式の右辺にはx+yやx^2+y^2などが現れるため、x,yから簡単な計算によって求めることができる。
【関連するAtcoderの問題例】
「Sum of Squares」
レーティング難易度(★): 900
ACした回答者に絞った場合のレーティング帯の範囲(数値): 428-1362
レーティング難易度(%): 56.8%
レーティング(数値): 1058
AC率(%): 81.2%
ACしたスコアの高い回答者: https://atcoder.jp/users/ainiy131
解説ブログ: https://www.hamayanhamayan.com/entry/2019/03/24/001424
「Rationality」
レーティング難易度(★): 1200
ACした回答者に絞った場合のレーティング帯の範囲(数値): 894-1545
レーティング難易度(%): 37.5%
レーティング(数値): 1223
AC率(%): 42.3%
ACしたスコアの高い回答者: https://atcoder.jp/users/rng_58
解説ブログ: https://motsu-xe.hatenablog.com/entry/2020/05/03/224042
Discussion