UVA 113 Power of Cryptography 解題詳解：大整數開根號的高效算法

問題背景

在現代密碼學研究中，大素數運算和模冪運算佔據核心地位。這些曾被視為純理論的數論成果，如今已廣泛應用於實際加密系統中。UVA 113「Power of Cryptography」正是針對大整數高效求根問題的經典題目。

題目大意

給定整數 n 和 p，求正整數 k 使得 kⁿ = p。題目保證 p 總是某個整數的 n 次方，且 1 ≤ n ≤ 200，1 ≤ p ≤ 10¹⁰¹。

核心挑戰

p 可高達 10¹⁰¹，遠超 64 位整數範圍（long long 最大約 10¹⁸）。常規整數類型無法直接存儲，需採用高精度或浮點數策略。

解法一：二分查找（需高精度乘法）

利用 k 的範圍在 1 到 10⁹ 之間，對 k 進行二分。每次驗證需計算 midⁿ 與 p 比較，這要求實現大整數乘法，代碼較繁瑣。

解法二：雙精度浮點數直接求根（推薦）

double 類型指數範圍達 10^±308，有效數字 15 位，完全覆蓋題目需求。通過誤差分析可證：f(p) = p^1/n 的最大誤差 Δ < 9×10^-7，取整後絕對準確。

#include <cstdio>
#include <cmath>
int main() {
    double n, p;
    while (scanf("%lf %lf", &n, &p) != EOF) {
        printf("%.0lf\n", pow(p, 1.0 / n));
    }
    return 0;
}

關鍵點總結

• 認清數據範圍，選擇合適數據類型（double 足矣）
• 利用數學庫函數 pow 直接計算，避免手寫高精度
• 輸出格式 %.0lf 自動四捨五入取整

這道題是「知識改變命運」的典型：了解浮點數特性，一行代碼解決看似棘手的大數問題。