プロジェクトオイラー601.

この記事の所要時間: 25

No.601 Divisibility streaks

問題.

正の数 n に対して, n+kk+1 で割り切れないような最小の整数 k をもって関数 streak(n)=k と定義しよう.

例えば:

13 は 1 で割り切れる

14 は 2 で割り切れる

15 は 3 で割り切れる

16 は 4 で割り切れる

17 は 5 で割り切れない

よって, streak(13)=4.

同様に,

120 は 1 で割り切れる

121 は 2 で割り切れない

よって, streak(120)=1

1<n<N を満たし, streak(n)=s である整数 n の個数を P(s, N) と定義する.

例えば, P(3, 14)=1, P(6, 10^6)=14286 となる.

では, i が 1 から 31 の範囲にあるときの P(i, 4^i) の和を求めよ.

考え方とプログラム例.

n+kk+1 で割り切れる \Leftrightarrow n-1k+1 で割り切れる

なので,

streak(n)=k \Leftrightarrow n-1k 以下のすべての自然数で割り切れて, k+1 では割り切れない

と言い換えることができます.

そこで, g0 を 1, 2, \ldots, k の最小公倍数, g1 を 1, 2, \ldots, k, k+1 の最小公倍数とすると, P(k, N)N 未満の整数のうち, g0 で割り切れて g1 で割り切れないものの個数となります.

今回は最大公約数を求める gcd をユークリッドの互除法で実装し, それを用いて最小公倍数 lcm を用意しました.

計算時間は 0.00013sec でした.

答えはこの下にあります. 反転してください.

A. 1617243

スポンサーリンク
sub2
sub2
  • このエントリーをはてなブックマークに追加