結果

問題 No.2 素因数ゲーム
コンテスト
ユーザー t8m8⛄️
提出日時 2015-08-10 18:15:10
言語 Haskell
(9.10.1)
結果
TLE  
実行時間 -
コード長 583 bytes
コンパイル時間 1,201 ms
コンパイル使用メモリ 174,976 KB
実行使用メモリ 13,880 KB
最終ジャッジ日時 2024-07-18 06:32:45
合計ジャッジ時間 9,436 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 6 TLE * 1 -- * 24
権限があれば一括ダウンロードができます
コンパイルメッセージ
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 Data.Bits

main = do
    n <- getLine
    let g = grundy (read n :: Int) $ sieve [2..(read n :: Int)]
    if g /= 0 then putStrLn "Alice" else putStrLn "Bob"

sieve :: [Int] -> [Int]
sieve [] = []
sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]

grundy :: Int -> [Int] -> Int
grundy x [] = 0
grundy x (p:ps)
        | cnt == 0 = 0 `xor` grundy x ps
        | otherwise = cnt `xor` (grundy (x `div` (p ^ cnt)) ps)
        where cnt = count x p

count :: Int -> Int -> Int
count x y = case x `mod` y of
                0 -> 1 + count (x `div` y) y
                _ -> 0;
0