突然ですが、問題です。を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をどーのこーのという方法もあるようだ。
最近のコメント