結果
問題 | No.312 置換処理 |
ユーザー |
|
提出日時 | 2019-01-18 20:02:36 |
言語 | Nim (2.2.0) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 3,537 bytes |
コンパイル時間 | 1,230 ms |
コンパイル使用メモリ | 72,448 KB |
最終ジャッジ日時 | 2024-11-14 20:46:46 |
合計ジャッジ時間 | 1,822 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
/home/judge/data/code/Main.nim(2, 28) Error: cannot open file: queues
ソースコード
import sequtils,strutils,algorithm,math,sugar,macros,strformatimport sets,tables,intsets,queues,heapqueue,bitopsconst 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 div 2 == 0: return falseif n == 2 or n == 3 or n == 5: return truelets = 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 squareFormFactor(n:int):int =if millerRabinIsPrime(n) : return nproc check(k:int):int =proc √(x:int):int = x.float.sqrt.intif n <= 1 : return nif n mod 2 == 0 : return 2if √(n) * √(n) == n : return √(n)var P,Q = newSeq[int]()block:P &= √(k * n)Q &= 1Q &= k * n - P[0]*P[0]while √(Q[^1]) * √(Q[^1]) != Q[^1]:let b = (√(k * n) + P[^1] ) div Q[^1]P &= b * Q[^1] - P[^1]Q &= Q[^2] + b * (P[^2] - P[^1])block:if Q[^1] == 0 : return check(k + 1)letb = (√(k * n) - P[^1] ) div Q[^1]P0 = b * √(Q[^1]) + P[^1]Q0 = √(Q[^1])Q1 = (k*n - P0*P0) div Q0(P,Q) = (@[P0], @[ Q0, Q1 ])while true:let b = (√(k * n) + P[^1] ) div Q[^1]P &= b * Q[^1] - P[^1]Q &= Q[^2] + b * (P[^2] - P[^1])if P[^1] == P[^2] or Q[^1] == Q[^2]: breaklet f = gcd(n,P[^1])if f != 1 and f != n : return felse: return check(k+1)return check(1)proc getFactors(n:int):seq[int]=if n == 1 : return @[1]if n == 0 : return @[0]result = @[]var m = nwhile true:let p = m.squareFormFactor()if p.millerRabinIsPrime(): result &= pelse: result &= p.getFactors()if p == m: returnm = m div pproc getchar_unlocked():char {. importc:"getchar_unlocked",header: "<stdio.h>" .}proc scan(): int =while true:var k = getchar_unlocked()if k < '0' or k > '9': breakelse: result = 10 * result + k.ord - '0'.ordlet n = scan()if n.millerRabinIsPrime(): quit $n, 0if n mod 2 == 0:let factors = (n div 2).getFactors().sorted(cmp)if factors[0] == 2 :if 3 in factors : echo 3else: echo 4else: echo factors[0]quit 0let factors = n.getFactors().sorted(cmp)echo factors[0]