自动搬运

查看原文

来自洛谷，原作者为

	hensier **

搬运于2025-08-24 22:23:04，当前版本为作者最后更新于2020-07-27 14:16:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

话休絮烦，我们直接对本题的做法进行分析。

Solution 1 部分分做法

期望得分：$25$ 分

当 $m=1$ 时，原式可转化为 $x^1 \le n$，即 $x \le n$。因为所有的 $x$ 都为正整数，所以直接输出 $n$ 即可。

Solution 2A, 2B: 求幂

期望得分：$75 \sim 100$ 分

我们可以很容易地想到暴力枚举。为了加速，我们可以使用快速幂。

然而，运算的结果连 unsigned long long 和 __int128_t 都会爆掉，所以这种方法行不通。

既然整型存不下，我们不妨使用 pow 函数来求解。该函数返回的值是双精度浮点数，即 double。

数据类型	关键字	大小	范围	有效数字
单精度	float	$4$ 字节	$[±3.4\times 10^{-38},±3.4\times 10^{38}]$	$7$ 位
双精度	double	$8$ 字节	$[±1.7\times 10^{-308},±1.7\times 10^{308}]$	$16$ 位

此处，返回的类型可以达到 $10^{308}$ 的数量级，所以根本不用担心范围问题。

不过，pow 函数包括大部分浮点运算都存在严重的精度缺失问题，因此不能保证答案完全正确：

printf("%.0lf",pow(27,18));
//输出结果为58149737003040063952519168

print(999 ** 6) # Python中a**b表示a^b
print(pow(27, 18))
# 输出结果均为58149737003040059690390169

我们知道，Python 的 int 自带高精度，因此不存在精度问题。这就恰恰印证了 pow 函数确实有精度上的缺失。

然而，虽然 pow 函数精度不高，但由于 $n,m \le 10^9$，因此对于本题来说，答案不会受到影响。如果范围扩大到 $10^{18}$，那么这种方法可能就不适用了。

代码：

#include<bits/stdc++.h>
int n,m;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;;i++)
    {
        if(pow(i,m)>n)
        {
            printf("%d",i-1);
            return 0;
        }
    }
    return 0;
}

Solution 3 求根

期望得分：$100$分

我们发现，当$x^m=n$的时候，$x$还可表示为$\sqrt[m]{n}$。因此输出答案为$\lfloor \sqrt[m]{n} \rfloor$。

由于$\sqrt[m]{n}=n^{\frac{1}{m}}$，所以使用 pow 函数即可求解：

#include<bits/stdc++.h>
int n,m;
int main()
{
    scanf("%d%d",&n,&m);
    printf("%.0f",pow(n,1.0/m));
    return 0;
}

Solution 4 对数

期望得分：$100$ 分

看到幂的运算，就能够想到对数。对数的定义：

如果 $a^x=N$（$a \gt 0$ 且 $a \neq 1$），则 $x=\log_a N$。

接下来就是对题目中不等号的处理。

不妨假设此时 $x^m=n$。由于答案为正整数，因此 $x$ 即为题目所求。根据对数的定义，有 $m=\log_xn$。

然而，一般编程语言的数学库只包含以 $e$ 为底、以 $2$ 为底和以 $10$ 为底的对数函数可供使用。

因此需要用到换底公式：

$$\log_ab=\dfrac{\log_cb}{\log_ca}(a>0,a \neq 1,c>0,c \neq 1) $$

把本题的数据代入得

$$\log_xn=\dfrac{\log_cn}{\log_cx}$$ $$m=\log_xn=\dfrac{\log_cn}{\log_cx}$$ $$\log_cx=\dfrac{\log_cn}{m}$$ $$x=c^{\frac{\log_cn}{m}}$$

由于 $x$ 大概率不是整数，因此需要对其进行下取整处理：

// 以 e 为底进行换底
#include<bits/stdc++.h>
int n,m;
int main()
{
    scanf("%d%d",&n,&m);
    printf("%.0f",floor(exp(log(n)/m))); // 必须加 floor 函数，因为 %.0f 默认四舍五入
    return 0;
}

// 以 2 为底进行换底
#include<bits/stdc++.h>
int n,m;
int main()
{
    scanf("%d%d",&n,&m);
    printf("%.0f",floor(pow(2,log2(n)/m)));
    return 0;
}

// 以 10 为底进行换底
#include<bits/stdc++.h>
int n,m;
int main()
{
    scanf("%d%d",&n,&m);
    printf("%.0f",floor(pow(10,log10(n)/m)));
    return 0;
}

Solution 5 二分

期望得分：$100$ 分

由于当指数为正时乘方具有单调性，因此可以使用二分答案。

因为 $x^m \le n$，所以 $x$ 一定不超过 $n$。由此可选取 $n$ 为初始上界。

题目中规定 $x$ 为正整数，因此可选取 $1$ 为初始下界。

二分每次需要判断 $\text{mid}^m$ 和 $n$ 的大小关系。如果前者大于后者，那么 $r=\text{mid}-1$，否则 $l=\text{mid}+1$。最后，在二分完全结束后，$r$ 即为所求。

// 二分配合快速幂
#include<bits/stdc++.h>
int n,m,l=1,r,mid;
bool check(long long x,long long y) // 这里可以用 long long 存储的原因是 res 只要稍大于 n（n <= 10^9），该函数将直接返回 false
{
    long long res=1;
    while(y)
    {
        if(x>n)return false;
        if(y&1)res*=x;
        if(res>n)return false;
        x*=x;
        y>>=1;
    }
    return res<=n;
}
int main()
{
    scanf("%d%d",&n,&m);
    r=n;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(check(mid,m))l=mid+1;
        else r=mid-1;
    }
    printf("%d",r);
    return 0;
}

// 二分配合 pow 函数
#include<bits/stdc++.h>
int n,m,l=1,r,mid;
int main()
{
    scanf("%d%d",&n,&m);
    r=n;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(pow(mid,m)<=n)l=mid+1; // 与上述同理，pow 函数的精度在 10^9 范围内可以接受
        else r=mid-1;
    }
    printf("%d",r);
    return 0;
}