結果

問題 No.16 累乗の加算
コンテスト
ユーザー mi_
提出日時 2016-05-07 14:25:22
言語 Fortran
(gFortran 14.2.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,552 bytes
コンパイル時間 1,318 ms
コンパイル使用メモリ 20,608 KB
最終ジャッジ日時 2024-11-15 04:44:18
合計ジャッジ時間 1,718 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
Main.f90:39:13:

   39 |     if (iand(b, 1) .eq. 1) then  ! bが奇数の場合、
      |             1
Error: Arguments of 'iand' have different kind type parameters at (1)
Main.f90:48:7:

   48 |   use module_modular
      |       1
Fatal Error: Cannot open module file 'module_modular.mod' for reading at (1): No such file or directory
compilation terminated.

ソースコード

diff #
raw source code 

!>
!! @brief 剰余演算(modular arthmeric)に関するアルゴリズムを扱う
!!
!! @note  剰余演算は、おおよそ、通常の整数上の演算とつぎの点を除けば同じであると考えてよい. すわなち、nを法とする剰余演算では、
!!        すべての結果xはn、を法としてxと等しい{0, 1, ..., n-1}の要素と置き換える. 加算、減算、乗算だけしか扱わなければ、
!!        この簡略な説明で十分である. 剰余演算の正確なモデルは群論の枠組みで記述するのが最善である
!!
!! @date  2016/05/07 
!!


module module_modular
  implicit none
  
  public :: modpow

contains

  !>
  !! @brief 反復2乗法(repeated squaring)によるべき乗剰余(modular exponetiation)の計算を扱います
  !!
  !! @note  Fortranでは引数は参照渡しとなるので非負整数a, bに対して破壊的代入を行うと面倒なことになる
  !!        そこで今回は再帰で反復2乗法を書くことにした
  !!
  recursive function modpow(a, b, n) result(d)
    implicit none

    integer(8), intent(in)  :: a, b, n
    integer(8) :: d

    if (b .eq. 0) then  ! 再帰の基底
       d = 1
       return
    end if

    d = modpow(mod(a * a, n), b / 2, n)
    ! bが偶数の場合、d^b = ((d^2)^(b/2))であるから、n/2の場合に帰着できる
    
    if (iand(b, 1) .eq. 1) then  ! bが奇数の場合、
       d = mod((d * a), n)       ! d^b = ((d^2)^(b/2)) * aであるから、n/2の場合に帰着できる
    end if
  end function modpow
  
  
end module module_modular

program main
  use module_modular
  implicit none

  integer(8) :: output, b, x, n, i
  integer(8), parameter :: m = 1000003
  character(9500)  input, output2
  character(100)   output1
  character(10), parameter :: delim = " "

  read(*,*) x, n  
  read(*, '(a)') input

  
  output = 0
  do i = 1, n
     call split(input, output1, output2, delim)
     input = output2

     read(output1, *) b 
     output = output + modpow(x, b, m)
     output = mod(output, m)
  end do
  
  write(*, '(I0)') output
contains

  
  subroutine split(input, output1, output2, delim)
    implicit none
    
    character(*), intent(inout) :: input
    character(*),  intent(out)  :: output1
    character(*), intent(out)   :: output2
    character(*),   intent(in)  :: delim
    integer :: index

    input = trim(input)

    index   = scan(input, delim)
    output1 = input(1:index-1)
    output2 = input(index+1:)
  end subroutine split
  
end program main
0