POJ-2109 Power of Cryptography(数学或二分+高精度)

时间:2023-02-02 15:07:01

题目链接:

https://vjudge.net/problem/POJ-2109

题目大意:

  1. 有指数函数 k^n = p , 
  2.        其中k、n、p均为整数且 1<=k<=10^9 , 1<=n<= 200 , 1<=p<10^101 
  3.        给定 n 和 p ,求底数 k 

思路:

一开始以为需要大数,没想到一个pow就行了,真是涨姿势

考虑到数值存储问题和精度问题,这题最直观的思路应该是使用 高精度算法 求解。
    而事实上,这题也可用公式法求解,但需要一些技巧。


    开方公式:k = n-sqrt(p)
    但C++的数学函数库并没有提供k次方的开方函数,此时需要转换一下公式:
        k = p^(1/n)

    对p开k次方等价于求p的1/k次方,此时我们就可以用pow函数求解了:
        k = pow(p, 1.0/n)


    其实严格来说,如果这题没有限制 底数k 是整数,就不可能通过公式投机取巧。
    简单来说,如果要使用公式法,那么题目中所有运算都只能基于double类型进行(int会溢出)

    double的取值范围为10^(-307)~10^308,但小数精度只有前16位(可自行搜索double的精度丢失问题).
    也是就说,当我们用double存储p的时候, 它就已经开始出现误差, 其误差范围在10^(-15)的数量级左右.

    此时套用公式对p开n次方根,须知开方运算是不会扩大误差范围的,
    所以 n-sqrt(p) 的小数位误差范围依旧在10^(-15)的数量级以内,
    又因为 k = n-sqrt(p) ,亦即计算所得的 n 的小数位误差范围也在10^(-15)的数量级以内,
    显然这个误差级数仅会对n的小数部分存在影响,四舍五入后对整数部分是无影响的.
    而题目已经限定了,n、k、p均是整数,因此使用公式法可以直接得到准确结果.

    假若题目不存在整数限制,当n极大时,k会极小(无限迫近1,对小数精度极高),
    此时公式法则会因为精度问题而失效.

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<cmath>
 6 #include<map>
 7 #include<queue>
 8 #include<stack>
 9 #define MEM(s, b) memset(a, b, sizeof(a));
10 using namespace std;
11 typedef long long ll;
12 int main()
13 {
14     double n, p;
15     while(cin >> n >> p)
16     {
17         double ans = pow(p, 1 / n);
18         int a = floor(ans + 0.5);
19         cout<<a<<endl;
20     }
21     return 0;
22 }

二分+高精度下次写吧