閱讀958 返回首頁    go 阿裏雲 go 技術社區[雲棲]

poj 2109 Power of Cryptography

今天懶了，這道題直接去看了大家的帖子，三行搞定。。。

題目大意： K ^ N = P, 給N 和 P， 求K。數據規模 ：1<=n<= 200, 1<=p<10101 and there exists an integer k, 1<=k<=109 。


看到1<=p<10101 我就去想大數操作了，後來發現原來double完全可以放。

類型          長度 (bit)           有效數字          絕對值範圍
float             32                      6~7                  10^(-37) ~ 10^38
double          64                     15~16               10^(-307) ~10^308
long double   128                   18~19                10^(-4931) ~ 10 ^ 4932

接下來就是直接用pow(n,1/p)就可以了，這個也可以開方。


一般思路：二分+高精度算法

 

但是本題還有一個更加巧妙的辦法去處理：

首先需要明確：double類型雖然能表示10^(-307)   ~   10^308, （遠大於題意的1<=p<10101這個範圍）,但隻能精確前16位，因此必須慎用！

那麼為了避免double對輸入的數在運算過程中進行精確，那麼我們必須讓double的運算第一步就得到一個int（即小數點尾數全為0），這個不難理解。

 

然後根據題意，是求指數k，一般人自然想到利用 對數log，即k=lognp。但是不要忘記使用對數最大的問題就是沒有lognp函數，隻有log()函數（底數為e），為此要計算lognp就必須使用換底公式lognp=log(p)/log(n),即k= log(p)/log(n)，由於這使得double的運算變為了3次，而且執行除法前的兩次對數運算log的結果未必都是int，很顯然k是一個被精確了的double

 

很多人到這裏就放棄了使用double，轉換方向到正常思路（二分+高精度算法），但是不要忘記求指數k除了使用對數log，還能使用指數的倒數開n次方，這時就可以用pow函數了

k=pow(p,1.0/n)，double的運算一步到位，k自然也是一個int


#include<iostream>
#include<math.h>

using namespace std;

int main(void)
{
	double n,p;

	while(cin>>n>>p)
		cout<<pow(p,1.0/n)<<endl;  //指數的倒數就是開n次方

	return 0;
}


還看到一種二分法，由p最大值最小值的中間值開始猜k，通過比較pow(k,n)與p的大小來進一步精確k，直到找到。

  1. #include<stdio.h>  
  2. #include<math.h>  
  3. #define eps 0.0000000001  
  4. void init(), work();  
  5. double n, m, k;  
  6. int main()  
  7. {  
  8.     init();  
  9.     return 0;  
  10. }  
  11. void init()  
  12. {  
  13.     while(scanf("%lf %lf", &n, &m) != EOF)  
  14.         work();  
  15. }  
  16. void work()  
  17. {  
  18.     long long left, right, mid;  
  19.     left = 0;  
  20.     right = 1000000002;  
  21.     while(left + eps < right){  
  22.         mid = (left + right) / 2;  
  23.         if(pow(mid, n) - m > 0)  
  24.             right = mid;  
  25.         else  
  26.             if(pow(mid, n) - m < 0)  
  27.                 left = mid;  
  28.             else{  
  29.                 printf("%.0ld\n", mid) ;  
  30.                 break;  
  31.             }  
  32.     }  
  33. }  




最後更新：2017-04-03 05:39:44

  上一篇：go HDU1016-Prime Ring Problem
  下一篇：go Cocos2d-x實例：設置背景音樂與音效-HelloWorld場景實現