結果
問題 | No.774 tatyamと素数大富豪 |
ユーザー |
|
提出日時 | 2019-02-05 06:49:03 |
言語 | Nim (2.2.0) |
結果 |
AC
|
実行時間 | 1,881 ms / 2,000 ms |
コード長 | 2,310 bytes |
コンパイル時間 | 3,112 ms |
コンパイル使用メモリ | 66,792 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-01 11:24:08 |
合計ジャッジ時間 | 12,456 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 14 |
コンパイルメッセージ
/home/judge/data/code/Main.nim(1, 27) Warning: imported and not used: 'strutils' [UnusedImport]
ソースコード
import sequtils,algorithm,strutils,mathtemplate times*(n:int,body) = (for _ in 0..<n: body)template `max=`*(x,y) = x = max(x,y)template `min=`*(x,y) = x = min(x,y)const INF = int.high div 4proc powerWhenTooBig(x,n:int,modulo:int = 0): int =proc mul(x,n,modulo:int):int =if n == 0: return 0if n == 1: return xresult = mul(x,n div 2,modulo) mod moduloresult = (result * 2) mod moduloresult = (result + x * (n mod 2 == 1).int) mod moduloif n == 0: return 1if n == 1: return xletpow_2 = powerWhenTooBig(x,n div 2,modulo)odd = if n mod 2 == 1: x else: 1if modulo > 0:const maybig = int.high.float.sqrt.int div 2if pow_2 > maybig or odd > maybig:result = mul(pow_2,pow_2,modulo)result = mul(result,odd,modulo)else:result = (pow_2 * pow_2) mod moduloresult = (result * odd) mod moduloelse:return pow_2 * pow_2 * oddproc millerRabinIsPrime(n:int):bool = # O(log n)proc ctz(n:int):int{.importC: "__builtin_ctzll", noDecl .} # 01<0000> -> 4proc power(x,n:int,modulo:int = 0): int =if n == 0: return 1if n == 1: return xlet pow_2 = power(x,n div 2,modulo)result = pow_2 * pow_2 * (if n mod 2 == 1: x else: 1)if modulo > 0: result = result mod moduloif n <= 1 : return falseif n == 2 or n == 3 or n == 5: return trueif n mod 2 == 0: return falselets = ctz(n - 1)d = (n - 1) div (1 shl s)var a_list = @[2, 7, 61]if n >= 4_759_123_141 and n < 341_550_071_728_321:a_list = @[2, 3, 5, 7, 11, 13, 17]if n in a_list : return truefor a in a_list:if powerWhenTooBig(a,d,n) == 1 : continuelet notPrime = toSeq(0..<s).allIt(powerWhenTooBig(a,d*(1 shl it),n) != n-1)if notPrime : return falsereturn trueproc getchar_unlocked():char {. importc:"getchar_unlocked",header: "<stdio.h>" .}proc scan(): int =while true:let k = getchar_unlocked()if k < '0': returnresult = 10 * result + k.ord - '0'.ordproc decode(A:seq[int]): int =for a in A:if a < 10: result = 10 * result + aelse:result = 100 * result + alet n = scan()var A = newSeqWith(n,scan()).sorted(cmp)var ans = -1while true:let p = A.decode()if ans < p and p.millerRabinIsPrime(): ans = pif not A.nextPermutation() : breakecho ans