没有按照Fermat的小定理得到预期输出

Question

根据Fermat的小定理，一个数的模乘逆如下所示

 a^(m-2) mod m if a and m are co-prime.

但我不会在下面的计划中得到预期的产出。在程序上哪一步是错误的？

 int pow_mod(int base,int pow,int MOD){
     long long int res = 1;
     while(pow){
       if(pow%2){
          res = (res*base)%MOD;
          pow--;
       }else{
          base = (base*base)%MOD;
          pow/=2;
       }
   }
   return res;
}
int main() {
   int mod = 100000007;
   cout<<(33 * pow_mod(11,mod-2,mod) ) %mod<<"\n";
    cout<<(33 / 11 ) %mod;

   return 0;
}

The Actual output : 
 
19692016
3

根据Fermat定理，在这两种情况下都应该是3。

Answer 1

碱基=(碱*碱)%MOD；

上面所有的操作数都是int，所以计算是用整数进行的。但是(假设32位整数)产品base * base最终会在循环期间溢出int范围。

下面的强制转换是强制计算使用long long int并生成正确结果的一种方法。

碱基=(基*(长长int)基)% MOD;