Code Jam 2008の問題

広告

突然ですが、問題です。1を1,000,000,000乗した結果の、整数部分の下3桁はどうなるでしょうか?

これは2008年のCode Jamの問題で難しい部類だそうです。

解答例

google

というわけで行列の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をどーのこーのという方法もあるようだ。

追記:続編出ました

こちらからどうぞ

3 件のコメント

  • 問題が面白かったのでちょっと自分でも考えてみました。
    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、…の範囲で繰り返し登場するみたいですね。

  • コメントを残す

    メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

    日本語が含まれない投稿は無視されますのでご注意ください。(スパム対策)