幂次进近

[编程题]幂次进近

热度指数：2586 时间限制：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

算法知识视频讲解

BeauWill

发表于 2026-02-04 00:14:27

可能不是正解！由于k>=1，n-pow(m, k)显然单调，于是想着二分查找第一个n-pow(m, k)大于0的m，然后比较此时二分结束的l和l - 1，答案m一定在这两之中用Python写就不需要实现高精度了，记得用PyPy3解释器，Python3解释器太慢了 import sys inp 展开全文

carson_flute

发表于 2026-02-04 12:09:27

题目描述给定正整数和，求一个正整数，使得最小。若存在多个使得差值相同，输出任意一个即可（通常取较小者，但本题数据保证唯一最优或按实现逻辑可过）。本题是考察整数快速幂 + 二分搜索 + 溢出防御的题，难度中等偏上核心思路核心观察函数在时是单峰函数：先递减后递增。展开全文

Silencer76

发表于 2026-02-04 09:42:15

三分注意区间右端点的取值，太大了会爆精度。 #include <iostream> #include <algorithm> #include <cmath> using namespace std; using ld=long double; using ll 展开全文

YunBaichuan

发表于 2026-02-04 11:18:53

思路：数学题，主要是精度和特判。第一个特判就是，此时令得到结果为0，这就是最小了；第二个特判就不好想了，当时，我们直接输出1即可，为什么？因为当时，对于来说，会超过题目的，并且差距会越来越大，所以说为了得到最小的结果，m只能取1 然后就可以直接算根了，为什么？因为题目给的是先减后增的，我们也可以在d 展开全文