結果

問題 No.186 中華風 (Easy)
ユーザー suisanka12
提出日時 2023-03-22 23:05:11
言語 Haskell
(9.10.1)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,309 bytes
コンパイル時間 8,654 ms
コンパイル使用メモリ 180,308 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-15 03:37:54
合計ジャッジ時間 9,710 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23
権限があれば一括ダウンロードができます
コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.8.2/environments/default
[1 of 2] Compiling Main             ( Main.hs, Main.o )
[2 of 2] Linking a.out

ソースコード

diff # 

--import qualified Geometry.Sphere as Sphere
{-# LANGUAGE BangPatterns #-}
import           Control.Monad
import qualified Data.ByteString.Char8 as BS
import           Data.Maybe
readInt :: BS.ByteString -> Int
readInt = fst . fromJust . BS.readInt
readIntList :: BS.ByteString -> [Int]
readIntList = map readInt . BS.words
getIntList :: IO [Int]
getIntList = readIntList <$> BS.getLine
main :: IO ()
main = do
    l <- replicateM 3 getIntList
    let p = [(i !! 0, i !! 1)|i <- l]
    let s = case solvemultiCRT p of Nothing -> -1
                                    Just (0, a) -> a
                                    Just (a, _) -> a
    print s
extGcd :: Int -> Int -> ((Int, Int), Int)
extGcd a 0 = ((1, 0), a)
extGcd a b = ((s, t-(a `quot` b)*s), g)
    where
        ((t, s), g) = extGcd b (a `rem` b)

solveCRT :: (Int, Int) -> (Int, Int) -> Maybe (Int, Int) -- (a, b)はa mod b
solveCRT (a1, n1) (a2, n2)
    |(a2-a1) `mod` r  /= 0 = Nothing
    |otherwise = Just ((n1*ans+a1)`mod`x, x)
    where
        ((p, _), r) = extGcd n1 n2
        ans = (a2-a1)`quot`r*p`rem`(n2`quot`r)
        x = (n1`quot`r)*n2

solvemultiCRT :: [(Int, Int)] -> Maybe (Int, Int)
solvemultiCRT [] = Just (0, 1)
solvemultiCRT (x:xs) = 
    case solvemultiCRT xs of
        Nothing -> Nothing
        Just t -> solveCRT t x
0