結果

問題 No.303 割れません
ユーザー kimiyuki
提出日時 2016-06-30 01:09:56
言語 Haskell
(9.10.1)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,032 bytes
コンパイル時間 323 ms
コンパイル使用メモリ 171,136 KB
最終ジャッジ日時 2024-11-14 19:46:04
合計ジャッジ時間 737 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、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:8:10: error: [GHC-39999]
    • Could not deduce ‘Semigroup (Mat22 a)’
        arising from the superclasses of an instance declaration
      from the context: Num a
        bound by the instance declaration at Main.hs:8:10-34
    • In the instance declaration for ‘Monoid (Mat22 a)’
  |
8 | instance Num a => Monoid (Mat22 a) where
  |          ^^^^^^^^^^^^^^^^^^^^^^^^^

Main.hs:19:20: error: [GHC-39999]
    • No instance for ‘Semigroup (Mat22 Integer)’
        arising from a use of ‘<>’
    • In the first argument of ‘go’, namely ‘(f <> f)’
      In the expression: go (f <> f) g (i `shift` 1)
      In the expression:
        if n .&. i == 0 then
            go (f <> f) g (i `shift` 1)
        else
            go (f <> f) (f <> g) (i `shift` 1)
   |
19 |         then go (f <> f)       g  (i `shift` 1)
   |                    ^^

ソースコード

diff # 

#!/usr/bin/env runhaskell
module Main where
import Data.Bits
import Data.Monoid

data Mat22 a = Mat22 a a a a deriving (Eq, Ord, Show, Read)

instance Num a => Monoid (Mat22 a) where
    mempty = Mat22 1 0 0 1
    mappend (Mat22 a00 a01 a10 a11) (Mat22 b00 b01 b10 b11)
        = Mat22 (a00 * b00 + a01 * b10) (a00 * b01 + a01 * b11) (a10 * b00 + a11 * b10) (a10 * b01 + a11 * b11)

fib :: Int -> Integer
fib n = unpack $ go f0 mempty 1 where
    f0 = Mat22 1 1 1 0
    go :: Mat22 Integer -> Mat22 Integer -> Int -> Mat22 Integer
    go _ g i | i > n = g
    go f g i = if n .&. i == 0
        then go (f <> f)       g  (i `shift` 1)
        else go (f <> f) (f <> g) (i `shift` 1)
    unpack (Mat22 a b c d) = b

solve :: Int -> Integer
solve l = if l `mod` 2 == 0
    then let h = l `div` 2 in 2 * fib (h-1) * fib h
    else fib l

main :: IO ()
main = do
    l <- readLn
    let y = solve l
    if y == 0
        then do
            print $ l+1
            putStrLn "INF"
        else do
            print l
            print y
0