0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

CodeIQ:「ルート・パワー問題」の解答

0
Posted at

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).    
  
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?