Kawazoe(@riverplus)さんのCodeIQの問題です。
元のページはリンク切れしていますが、こちらに問題と解答、解説が載っています。
->http://charleworld.air-nifty.com/blog/2015/12/codeiqkawazoe-1.html
ここにも情報があります。
->https://posfie.com/@riverplus/p/AxeCL8Y
問題->(1+√2+√3+√5)^n の有理数の項を求めよというもの。
問題からは整数と√(2,3,5,6,10,15,30)の項しか生じないので、
√(2,3,5,6,10,15,30)に次々(1,√2,√3,√5)を掛けて行ってその漸化式を作ります。
掛けられる方が a+b√2+c√3+d√5+e√6+f√10+g√15+h√30 なら
1+√2+√3+√5を掛けると
整数項はa+b√2^2+c√3^2+d+d√5^2 = 1+2b+3c+5d
√2の項はa√2+b√2*1+e√6*√3+f√10*√5 = (a+b+3e+5f)*√2
以下同様にして
a1 = a+2b+3c+5d
b1 = a+b+3e+5f
c1 = a+c+2e+5g
d1 = a+d+2f+3g
e1 = b+c+e+5h
f1 = b+d+f+3h
g1 = c+d+g+2h
h1 = e+f+g+h
さらに a = a1,b = b1,....h = h1
のようになります。
これを繰り返せば答えは出ますが、大きい数では時間がかかりますので、
行列のべき乗を使って表し、更に二乗法を使って時間を短縮します。
->https://ja.wikipedia.org/wiki/%E5%86%AA%E4%B9%97(冪乗)
コンピュータのアルゴリズムとして書くとこうなる。
指数を n とし、2乗していく値 p := a、結果値 v := 1 とする。
n が 0 なら、v を出力して終了する。
n の最下位桁が 1 なら、v := v * p とする。
n := [n/2] とし(端数切捨て)、 p := p * p として、2. に戻る。
二乗法の関数(bpower)でついでに剰余も求めます。
arは書きやすいのでこのように書きましたが、掛けるときは転置します。
Juliaでは 行列a,bの積はa*bです。またa'はaの転置行列です。
求めるのは整数ですので、計算結果のベクトルの最初の値になります。
#julia ver 1.41,1.53,1.85,1.12.1
function solve(n,a)
function bpower(n,v,p)
if n == 0
return v
elseif n & 1 == 1
v = map(x->mod(x,m),v*p)
end
p = map(x->mod(x,m),p*p)
return bpower(n >> 1 ,v,p)
end
m=10^7
ve=[1 1 1 1 0 0 0 0]
#a+b*√2+c*√3+d*√5+e*√6*f*√10+g*√15+h*√30
ar=[1 2 3 5 0 0 0 0
1 1 0 0 3 5 0 0
1 0 1 0 2 0 5 0
1 0 0 1 0 2 3 0
0 1 1 0 1 0 0 5
0 1 0 1 0 1 0 3
0 0 1 1 0 0 1 2
0 0 0 0 1 1 1 1]
v = [1 1 1 1 0 0 0 0]
ar1 = bpower(n-1,v,ar')
ans = mod((ar1)[1],m)
s = ans == a ? "ok " : "no "
println(s,ans)
end
solve(12,7862325)
solve(1000,1730937)
solve(9998513322,8644803)
前々回に登場したPicatに移してみました。今回は関数表記を使いました。
Picatには行列の積の関数はないようですが、二次元配列二つと内包表記を
用いて表せます。(mprod)ついでに剰余も求めます。
%Picat 3.9#7 ,vscode
main => start.
makes(N,R,A) =>
Str = cond(R == A, " ok ", " no "),
printf(" %s %w->%w%n", Str, N, R).
mprod(Ar1,Ar2) = R => %行列の積
R =[[(sum([Ar1[X,I]*Ar2[I,Y] :I in 1..Ar1[1].len]) mod 10000000)
: Y in 1..Ar2[1].len]:X in 1..Ar1.len].
power(0,V,_) = V. %二乗法
power(N,V,P) = R =>
if N mod 2 =:= 1 then V := mprod(V,P) end,
R = power(N div 2,V,mprod(P,P)).
trans(M) = R => %行列の転置
R = [[M[I,J] : I in 1..M.len] : J in 1..M[1].len].
% Trans = transpose(M). %転置の関数はあるがutilが必要
start ?=> % ? があるとバックトラックする
f(N,A),
if solve(N, R) then makes(N,R,A)
else printf(" fail %w%n", N) end,
fail.
start => true.
solve(N,R) =>
Ar0=[[1, 2, 3, 5, 0, 0, 0, 0],
[1, 1, 0, 0, 3, 5, 0, 0],
[1, 0, 1, 0, 2, 0, 5, 0],
[1, 0, 0, 1, 0, 2, 3, 0],
[0, 1, 1, 0, 1, 0, 0, 5],
[0, 1, 0, 1, 0, 1, 0, 3],
[0, 0, 1, 1, 0, 0, 1, 2],
[0, 0, 0, 0, 1, 1, 1, 1]],
Ve = [[1,1,1,1,0,0,0,0]],
Ar = power(N-1,Ve,trans(Ar0)),
R = Ar[1,1].
f(12,7862325).
f(1000,1730937).
f(9998513322,8644803).