結果

問題 No.526 フィボナッチ数列の第N項をMで割った余りを求める
ユーザー こまるこまる
提出日時 2020-10-24 15:47:02
言語 Haskell
(9.10.1)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,538 bytes
コンパイル時間 300 ms
コンパイル使用メモリ 158,208 KB
最終ジャッジ日時 2024-11-14 23:52:51
合計ジャッジ時間 832 ms
ジャッジサーバーID
(参考情報)
judge3 / judge5
このコードへのチャレンジ
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.8.2/environments/default
[1 of 2] Compiling Main             ( Main.hs, Main.o )

Main.hs:39:32: error: [GHC-87543]
    Ambiguous occurrence ‘.>>.’.
    It could refer to
       either ‘Data.Bits..>>.’,
              imported from ‘Data.Bits’ at Main.hs:4:1-26,
           or ‘Main..>>.’, defined at Main.hs:57:1.
   |
39 |       (a, b) = fastDoubling (i .>>. 1) m
   |                                ^^^^

ソースコード

diff #
プレゼンテーションモードにする

{-# LANGUAGE MagicHash #-}
{-# LANGUAGE UnboxedTuples #-}
import Data.Bits
import GHC.Exts
main :: IO ()
main = do
[n, m] <- map read . words <$> getLine
print $ fibMod (n - 1) m
plusMod :: Int -> Int -> Int -> Int
plusMod (I# x#) (I# y#) (I# m#) = case x# +# y# of
r# -> I# (r# -# ((r# >=# m#) *# m#))
{-# INLINE plusMod #-}
minusMod :: Int -> Int -> Int -> Int
minusMod (I# x#) (I# y#) (I# m#) = case x# -# y# of
r# -> I# (r# +# ((r# <# 0#) *# m#))
{-# INLINE minusMod #-}
mulMod :: Int -> Int -> Int -> Int
mulMod (I# x#) (I# y#) (I# mo#) = case timesWord# (int2Word# x#) (int2Word# y#) of
z# -> case timesWord2# z# im# of
(# q#, _ #) -> case minusWord# z# (timesWord# q# m#) of
v# | isTrue# (geWord# v# m#) -> I# (word2Int# (plusWord# v# m#))
| otherwise -> I# (word2Int# v#)
where
m# = int2Word# mo#
im# = plusWord# (quotWord# 0xffffffffffffffff## m#) 1##
{-# INLINE mulMod #-}
fastDoubling :: Int -> Int -> (Int, Int)
fastDoubling 0 _ = (0, 1)
fastDoubling 1 _ = (1, 1)
fastDoubling i m
= let
(a, b) = fastDoubling (i .>>. 1) m
p = mulMod a a m
q = mulMod b b m
r = mulMod 2 a m
s = mulMod 2 b m
x = minusMod s a m
y = plusMod r b m
in
if even i
then (mulMod a x m, plusMod p q m)
else (plusMod p q m, mulMod b y m)
fibMod :: Int -> Int -> Int
fibMod i m = case fastDoubling i m of (a, _) -> a
infixl 8 .>>.
(.>>.) :: Bits b => b -> Int -> b
(.>>.) = unsafeShiftR
{-# INLINE (.>>.) #-}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0