結果
問題 | No.16 累乗の加算 |
ユーザー |
|
提出日時 | 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言語の場合は開発者のデバッグのため、公開されます。
ただし、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.
ソースコード
!>!! @brief 剰余演算(modular arthmeric)に関するアルゴリズムを扱う!!!! @note 剰余演算は、おおよそ、通常の整数上の演算とつぎの点を除けば同じであると考えてよい. すわなち、nを法とする剰余演算では、!! すべての結果xはn、を法としてxと等しい{0, 1, ..., n-1}の要素と置き換える. 加算、減算、乗算だけしか扱わなければ、!! この簡略な説明で十分である. 剰余演算の正確なモデルは群論の枠組みで記述するのが最善である!!!! @date 2016/05/07!!module module_modularimplicit nonepublic :: modpowcontains!>!! @brief 反復2乗法(repeated squaring)によるべき乗剰余(modular exponetiation)の計算を扱います!!!! @note Fortranでは引数は参照渡しとなるので非負整数a, bに対して破壊的代入を行うと面倒なことになる!! そこで今回は再帰で反復2乗法を書くことにした!!recursive function modpow(a, b, n) result(d)implicit noneinteger(8), intent(in) :: a, b, ninteger(8) :: dif (b .eq. 0) then ! 再帰の基底d = 1returnend ifd = 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 ifend function modpowend module module_modularprogram mainuse module_modularimplicit noneinteger(8) :: output, b, x, n, iinteger(8), parameter :: m = 1000003character(9500) input, output2character(100) output1character(10), parameter :: delim = " "read(*,*) x, nread(*, '(a)') inputoutput = 0do i = 1, ncall split(input, output1, output2, delim)input = output2read(output1, *) boutput = output + modpow(x, b, m)output = mod(output, m)end dowrite(*, '(I0)') outputcontainssubroutine split(input, output1, output2, delim)implicit nonecharacter(*), intent(inout) :: inputcharacter(*), intent(out) :: output1character(*), intent(out) :: output2character(*), intent(in) :: deliminteger :: indexinput = trim(input)index = scan(input, delim)output1 = input(1:index-1)output2 = input(index+1:)end subroutine splitend program main