给定一个整数 w，找到 n 和 k 使得 n^k = w

Question

我正在处理一个 Uva 问题 (#107)，我知道我有正确的答案，现在我只需要优化它，这样它就不会超时。我相信这个片段是罪魁祸首。我需要找到 n 和 k 使得 n^k = 工作。我尝试制作自己的电源功能来加速它，但这没有帮助。有哪些方法可以快速计算等于给定值的底数和指数？

N = 2;
for(int i = 1; i < range; i++){
    result = pow(N, i);

    if(result > working){
        i = 1;
        N++;
    }

    if(result == working){
        k = i;
        break;
    }
}

Answer 1

您可以尝试 k >= 2 并用 sqrt(w) 限制 N，在 2 开始 i环形。如果未找到解决方案，则 k = 1、n = w。此外，您不需要 pow，您可以在每次迭代中将中间产品乘以 N。