幂次进近

[编程题]幂次进近

热度指数：4 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定 $t$ 次询问，每次询问给出两个正整数 $n$ 和 $k$ 。
请你找到最小的正整数 $m$ ，使得 $n-m^k$ 的绝对值最小。

输入描述:

第一行有一个整数  。
随后  行，每行两个整数  。

输出描述:

输出  行，每行一个正整数  。

示例1

输入

输出

2
1
4

示例2

输入

3
114 514
1000000000 2
1000000000000000000 3

输出

1
31623
1000000

备注:

如果你使用 python 编写代码，请提交到 pypy3

算法知识视频讲解

kilomatutinal

我讨厌这道题

发表于今天 11:22:29 回复(3)

pandaC222

本题数比较大，所以可以用py解决，但是py也需要特判三个点，不然会超时

k=1时直接输出n

k>60直接输出1，因为(2**61 > 1e18)，大于 60 的 k，整数根可能只有 1

n=1直接输出1

代码如下：

作者：pandaC222
链接：https://www.nowcoder.com/discuss/848563961992581120

来源：牛客网

def fastpow(a,b):
    ans=1
    while b!=0:
        if b&1:
            ans*=a
        b>>=1
        a*=a
    return ans
t=int(input())
for _ in range(t):
    n,k=map(int,input().split())
    if k==1:
        print(n)
        continue
    if n==1&nbs***bsp;k>60:
        print(1)
        continue
    l=0
    r=10**18
    while l+1<r:
        mid=(l+r)//2
        if fastpow(mid,k)<=n:
            l=mid
        else:
            r=mid
    res1=abs(n-fastpow(l,k))
    res2=abs(n-fastpow(l+1,k))
    if res1>res2:
        print(l+1)
    else:
        print(l)

发表于今天 14:10:49 回复(0)