题解 P2293 【[HNOI2004]高精度开根】

PragmaGCC · 2020-06-13 23:23:39 · 题解

我们无论遇到什么高精！
也不要怕！
微笑着面对它！
消除高精的最好方法就是用python！

开根，首选pow，但是无论是c++还是py的pow都很慢，还容易出锅，所以另外考虑方法——二分

m = int(input())
n = int(input())
l = 0
#需要注意的是，这里如果l不是0的话第二个点会WA掉
#或者加一个特判也可以
r = 1
if m==0:
    print("err, I can't solve it")
while r**m <= n:
    l = r
    r = r<<1
while l+1 < r:        #必须是<
    mid = (l+r)>>1
    if mid**m <= n:   #必须是<=
        l = mid
    else:
        r = mid

if l**m <= n:
    print(l)
else:
    print(r)