递归程序不适用于大输入

Question

我试图从这个网站写一个问题的答案 - https://main2.edu.pl/c/kurs-podstaw-algorytmiki-druga-e/p/kro/

这是关于递归课程的补充，所以我想出了一个使用它的代码。它应该显示(a+1)^b modulo-10000 余数。不幸的是，对于小数字，我的程序有效，但是当它达到更大的数字时，它只是......不会 - 例如：

a = 1
b = 4
输出是16，这是正确的。

a = 2
b = 3
输出是27，这是正确的。

a = 2
b = 100
它给了我输出-8495，这是完全不正确的。

我试图寻找它，但我没有找到解决我的问题的正确方法，因为我真的不知道发生了什么。我在想，也许是因为数据类型太小，但将int更改为long int，并没有改变任何东西。

这是我的代码：

#include <iostream>
using namespace std;

int pot(int a, int b){
    if (b == 1)
        return a;
    if (b % 2 == 0) //test for even number
        return pot(a, b / 2) * pot(a, b / 2);
    else //make it even number
        return a * pot(a, b - 1);
}

main(){
    int a, b;
    int P;
    cin>>P;
    for(int i = 1; i<=P; i++){
        a = 0;
        b = 0;
        cin>>a;
        cin>>b;
        cout<<endl<<(pot(a+1, b))%10000;
    }
}

Answer 1

而不是只取最终结果的余数，你应该在每次pot返回一个值时取它。结果应该是正确的，因为你只是通过事情乘以结果，并(x*y) % m应等于((x % m) * (y % m)) % m为阳性x，y和m。

尝试这个：

int pot(int a, int b){
    int r;
    if (b == 1)
        r = a;
    else if (b % 2 == 0) //test for even number
        r = pot(a, b / 2) * pot(a, b / 2);
    else //make it even number
        r = a * pot(a, b - 1);
    return r % 10000;
}

此外，您正在复制pot(a, b / 2)第二种情况下的计算，这将大大减慢它的速度。你应该改变：

r = pot(a, b / 2) * pot(a, b / 2);

到：

r = pot(a, b / 2);
r *= r;

（当然还要加上花括号。）那应该快得多。

更新：我刚刚更正了我的答案，以包含else原始代码中不存在的第二种情况。原始代码中不需要它，但在我更改后需要它。