c++ - 递归在指数平方中的工作？

Question

我正在阅读 codechef 教程中用于快速乘法的指数平方法，我对此方法没有什么疑问

long long int fast_exp(int base, int exp)
{
if(exp==1)
return base;
else
{
    if(exp%2 == 0)
    {
        long long int base1 = pow(fast_exp(base, exp/2),2);
        if(base1 >= 1000000007)
        return base1%1000000007;
        else
        return base1;
    }
    else
    {
        long long int ans = (base*  pow(fast_exp(base,(exp-1)/2),2));
        if(ans >= 1000000007)
        return ans%1000000007;
        else
        return ans;
    }
  }
} 

我的疑问是这个方法是在每个递归步骤还是在计算实际base^exp后的最后一步执行'%'操作.我个人认为它在最后一步以及我针对

运行这段代码时计算了 %

base=345 and exp=246;

它给了我垃圾值(value)。

我想知道当'%'操作发生时，在每一步或只是在最后一步。

Answer 1

你的问题有点令人困惑，所以我实际上不知道你想问什么，但我确实看到你的代码存在三个主要问题:

• pow 是 float 幂，这意味着当数字足够大时会出现舍入误差。当您尝试进行精确的整数运算时，您不能使用它。
• 您似乎正在尝试对特定的 30 位模数进行算术运算，这意味着将三个减少的数量相乘(例如，将一个数平方然后乘以另一个数)将得到最多 90 位的结果，因此会溢出long long，因为它可能只是一个 64 位类型。
• 您使用的是有符号类型，但您的所有代码似乎都假设您的所有数字都是非负数。