k-th Root (Integer) - Githubissues

kemuniku commented 3 weeks ago

2分探索？

kemuniku commented 2 weeks ago

https://judge.yosupo.jp/problem/kth_root_integer

kemuniku commented 2 weeks ago

proc inner_mul_overflow(a:int,b:int,c:ptr int):bool{.importcpp:"__builtin_mul_overflow(#,#,#)"}
proc mul_overflow(a:int,b:int,c:var int):bool=
    return inner_mul_overflow(a,b,c.addr)

こういうのがあれば便利なのかもしれない(オーバーフローチェックに)

kemuniku commented 2 weeks ago

uintじゃないといけないらしいです

kemuniku commented 2 weeks ago

include cplib/tmpl/sheep
import cplib/utils/binary_search

proc inner_umul_overflow(a:uint,b:uint,c:ptr uint):bool{.importcpp:"__builtin_umull_overflow(#,#,#)".}
proc mul_overflow(a:uint,b:uint,c:var uint):bool=inner_umul_overflow(a,b,c.addr)

proc is_ok(arg:uint,A:uint,k:int):bool=
    var now = uint(1)
    for _ in 0..<k:
        if mul_overflow(now,arg,now):
            return false
    return now <= A

proc kth_root(A:uint,k:int):uint=
    if A <= 1 or k == 1:
        return A
    if k >= 64:
        return 1
    var tmp = uint(pow(float(A),1/k))
    while is_ok(tmp,A,k):
        tmp += 1
    return tmp-1
proc ui(): uint {.inline.} = scanf("%llu\n", addr result)
var T = ii()
for i in 0..<T:
    var A = ui()
    var k = ii()
    echo kth_root(A,k)

これで通るんだけど、正当性確認してないです...

kemuniku / cplib

k-th Root (Integer) #300