P6685 可持久化动态仙人掌的直径问题 题解

· · 题解

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

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;
}