Project Euler - Problem 340
Crazy Function
固定された整数 a, b, c に対し, crazy function F(n) を次のように定義する：
F(n) = n - c （n > b のとき）
F(n) = F(a + F(a + F(a + F(a + n)))) （n ≤ b のとき）
また, S(a, b, c) = $ \displaystyle \sum_{n = 0}^{b} F(n) $ と定義する.
例えば, a = 50, b = 2000, c = 40 なら, F(0) = 3240 および F(2000) = 2040 である.
また, S(50, 2000, 40) = 5204240 である.
S(217, 721, 127) の下 9 桁を求めよ.
(日本語訳より)
F(n) = n - c （n > b のとき）
F(n) = F(a + F(a + F(a + F(a + n)))) （n ≤ b のとき）
また, S(a, b, c) = $ \displaystyle \sum_{n = 0}^{b} F(n) $ と定義する.
例えば, a = 50, b = 2000, c = 40 なら, F(0) = 3240 および F(2000) = 2040 である.
また, S(50, 2000, 40) = 5204240 である.
S(217, 721, 127) の下 9 桁を求めよ.
(日本語訳より)
くそでかい数が出てきたらだいたい周期性があると思っていい
このように ( a = 194, b = 2000, c = 70 の場合 )
注意深く観察すると (注意深く観察してください)
こんな感じのことがわかるので，$ \displaystyle q = \left\lfloor \frac{ b }{ a } \right\rfloor, \ r = b \ \% \ a $ とすれば，
$ S(a, b, c) $
$ = (qa + r + 1)(4a + b - 4c) $
$ \displaystyle \qquad + 3(a - c) \left( \frac{ q(q - 1) }{ 2 } a + q(r + 1) \right) $
$ \displaystyle \qquad - \frac{ a(a - 1) }{ 2 } q - \frac{ r(r + 1) }{ 2 } $
ですね
