根据费马小定理没有得到预期的输出

Question

根据费马小定理可以求出一个数的模乘逆

 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

根据费马定理，这两种情况都应该是 3。

Answer 1

base = (base*base)%MOD;

上面的所有操作数都是int所以计算是以整数来完成的。但是（假设是 32 位整数）乘积 base * base 最终会在循环期间溢出 int 范围。

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

base = (base * (long long int)base) % MOD;

根据费马小定理没有得到预期的输出

Not getting expected output as per Fermat's little theorem

c++

math

multiplication

inverse

modulo