Close Menu Navigation
Open Categories Menu Code Jam 2008の問題
- 20 8月, 2009 -
- Google Code Jam, ニート, ニート脱出, プログラミング, 就職活動 -
- Tags :
- 3 Comments
突然ですが、問題です。
を1,000,000,000乗した結果の、整数部分の下3桁はどうなるでしょうか?
これは2008年のCode Jamの問題で難しい部類だそうです。
解答例
というわけで行列のn乗を求めて左上成分を2倍して1を引けばよい。下3桁しか興味がないのでmod 1000してしまう。
require 'matrix' # 行列の要素へのアクセスを定義 class Matrix def []=(i,j,x) @rows[i][j]=x end end # 行列のn乗を計算 def exponentiation(matrix, n) if n == 1 then return matrix end if n % 2 == 0 then m = exponentiation(matrix, n/2) result = m * m else m = exponentiation(matrix, n-1) result = matrix * m end result[0,0] = result[0,0] % 1000 result[1,0] = result[1,0] % 1000 result[0,1] = result[0,1] % 1000 result[1,1] = result[1,1] % 1000 return result end m = Matrix[[3,5],[1,3]] puts ( 2 * exponentiation(m,1000000000)[0,0] -1 ) % 1000
答えは751だそうだ。
余談
puts ( 2 * exponentiation(m,10)[0,0] -1 ) % 1000 puts ( 2 * exponentiation(m,100)[0,0] -1 ) % 1000 puts ( 2 * exponentiation(m,1000)[0,0] -1 ) % 1000 puts ( 2 * exponentiation(m,10000)[0,0] -1 ) % 1000 puts ( 2 * exponentiation(m,100000)[0,0] -1 ) % 1000 puts ( 2 * exponentiation(m,1000000)[0,0] -1 ) % 1000 puts ( 2 * exponentiation(m,10000000)[0,0] -1 ) % 1000 puts ( 2 * exponentiation(m,100000000)[0,0] -1 ) % 1000 puts ( 2 * exponentiation(m,1000000000)[0,0] -1 ) % 1000
しても結果は
47 751 751 751 751 751 751 751 751
と100乗より先は全部751である。たぶんバカ正直に計算しなくてもある程度大きいところなら結果は同じということに気づけばもっとエレガントに答えが出るのかも知れない。
中国の剰余定理を使ってXn mod 8とXn mod 125からXn mod 1000をどーのこーのという方法もあるようだ。
追記：続編出ました
- 著者／訳者：ティモシー・フェリス
- 出版社：青志社( 2011-02-03 )
- 単行本：640 ページ
- ISBN-10 : 4905042097
- ISBN-13 : 9784905042099
- 定価：￥ 1,995
プログラミングコンテストチャレンジブック [第2版] ～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～
- 著者／訳者：秋葉拓哉 岩田陽一 北川宜稔
- 出版社：マイナビ( 2012-01-28 )
- 単行本（ソフトカバー）：368 ページ
- ISBN-10 : 4839941068
- ISBN-13 : 9784839941062
- 定価：￥ 3,444
問題が面白かったのでちょっと自分でも考えてみました。
X(i)=(3+5^0.5)^i+(3-5^0.5)^iとします。
X(i+1)=6*X(i)-4*X(i-1)
という漸化式を得られます(X(i)の両辺に((3+5^0.5)+(3-5^0.5))をかけてうまくまとめてみてください)。
これでX(0)=2、X(1)=6より、以降のX(i)を計算できます。また、下3けたに
注目するので、X(i+1)の下3けたは、X(i),X(i-1)の下3けたを使えばいいです。
これでもあってそうですかね？後でエクセルで計算してみます。
エクセルで確認してみました。
X(100)の下3けた=752
X(101)の下3けた=256
X(200)の下3けた=752
X(201)の下3けた=256
より、2つ連続で下3桁が一致するので、X(100)～(199)の下3桁が
200～299、300~399、400~499、…の範囲で繰り返し登場するみたいですね。
ありがとうございます、それいけそうです。というわけで続編書きました。