c++ - 递归程序不适用于大输入

Question

我试图从此站点写一个问题的答案-https://main2.edu.pl/c/kurs-podstaw-algorytmiki-druga-e/p/kro/
这是关于递归的一课的补充，因此我想出了一个使用递归的代码。它应该显示(a + 1)^ b模余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，而原始代码中没有这种情况。原始代码中不需要它，但是在我进行更改之后就需要它。