a671 - 00113 - Power of Cryptography

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算整數 p 的 n 次方根，已知 p 可以表示成 k 的 n 次方，其中 k 也是整數。換句話說，需要找到 k 使得 k^n = p。

解題思路

題目給定 p 和 n，要求 k。由於 k^n = p，可以對等式兩邊取對數，得到 n * log(k) = log(p)，因此 log(k) = log(p) / n，進而 k = exp(log(p) / n)。由於題目要求輸出整數 k，需要將計算結果四捨五入到最接近的整數。

複雜度分析

• 時間複雜度: O(1)
• 空間複雜度: O(1)

程式碼

#include <iostream>
#include <cmath>
using namespace std;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	double a,b;
	while(cin >> a >> b)
		cout << (int)(exp(log(b)/a)+0.5) << "\n";
}