Code Jam 2008の問題

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

追記：続編出ました

こちらからどうぞ