結果

問題 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言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
/home/judge/data/code/Main.nim(2, 28) Error: cannot open file: queues

ソースコード

diff #
プレゼンテーションモードにする

import sequtils,strutils,algorithm,math,sugar,macros,strformat
import sets,tables,intsets,queues,heapqueue,bitops
const INF = int.high div 4
proc powerWhenTooBig(x,n:int,modulo:int = 0): int =
proc mul(x,n,modulo:int):int =
if n == 0: return 0
if n == 1: return x
result = mul(x,n div 2,modulo) mod modulo
result = (result * 2) mod modulo
result = (result + x * (n mod 2 == 1).int) mod modulo
if n == 0: return 1
if n == 1: return x
let
pow_2 = powerWhenTooBig(x,n div 2,modulo)
odd = if n mod 2 == 1: x else: 1
if modulo > 0:
const maybig = int.high.float.sqrt.int div 2
if 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 modulo
result = (result * odd) mod modulo
else:
return pow_2 * pow_2 * odd
proc millerRabinIsPrime(n:int):bool = # O(log n)
proc ctz(n:int):int{.importC: "__builtin_ctzll", noDecl .} # 01<0000> -> 4
proc power(x,n:int,modulo:int = 0): int =
if n == 0: return 1
if n == 1: return x
let 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 modulo
if n <= 1 : return false
if n div 2 == 0: return false
if n == 2 or n == 3 or n == 5: return true
let
s = 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 true
for a in a_list:
if powerWhenTooBig(a,d,n) == 1 : continue
let notPrime = toSeq(0..<s).allIt(powerWhenTooBig(a,d*(1 shl it),n) != n-1)
if notPrime : return false
return true
proc squareFormFactor(n:int):int =
if millerRabinIsPrime(n) : return n
proc check(k:int):int =
proc(x:int):int = x.float.sqrt.int
if n <= 1 : return n
if n mod 2 == 0 : return 2
if(n) *(n) == n : return(n)
var P,Q = newSeq[int]()
block:
P &=(k * n)
Q &= 1
Q &= 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)
let
b = ((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]: break
let f = gcd(n,P[^1])
if f != 1 and f != n : return f
else: 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 = n
while true:
let p = m.squareFormFactor()
if p.millerRabinIsPrime(): result &= p
else: result &= p.getFactors()
if p == m: return
m = m div p
proc getchar_unlocked():char {. importc:"getchar_unlocked",header: "<stdio.h>" .}
proc scan(): int =
while true:
var k = getchar_unlocked()
if k < '0' or k > '9': break
else: result = 10 * result + k.ord - '0'.ord
let n = scan()
if n.millerRabinIsPrime(): quit $n, 0
if n mod 2 == 0:
let factors = (n div 2).getFactors().sorted(cmp)
if factors[0] == 2 :
if 3 in factors : echo 3
else: echo 4
else: echo factors[0]
quit 0
let factors = n.getFactors().sorted(cmp)
echo factors[0]
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0