c++ - 代码中需要澄清，底层数学是什么？

Question

需要解决一个问题来计算

a^b mod p where  a,b <= 10 ^ 100000
MOD = 1000000007

在每个测试用例中，a 和 b 都以符合上述限制的数字字符串形式给出。我尝试使用下面提到的使用指数调制的代码来解决它。

typedef long long ll;
ll modPow(ll base, ll exp, ll n) {
    base = base%n;
    if (exp == 0)
        return 1;
    else if (exp == 1)
        return base;
    else if (exp % 2 == 0)
        return modPow(base * base % n, exp / 2, n);
    else
        return base * modPow(base, exp - 1, n) % n;
 }

 int main() {
     ll test, i, j , k;
     string a, b; 
     ll x, y, ans;
     cin >> test ;
     while ( test-- ) {
         cin >> a >> b;
         x = 0;
         for (i = 0; i < a.length(); i++)
             x = (x * 10 + (a[i] - '0')) % MOD;
         y = 0 ;

         for (i = 0 ; i < b.length(); i++)
             y = (y * 10 + (b[i] - '0')) % (MOD - 1);

         // cout << x <<" "<< y << endl;
         ans = modPow(x, y, MOD);
         cout << ans % MOD << endl ;
     }
}

我只想知道在计算指数值y时，我们为什么这样做

for (j = 0; j < b.length(); j++)
    y = ( ( y * 10 ) + ( b[i] - '0') ) % (MOD-1); // gave correct answer

代替

for (j = 0; j < b.length(); j++)
    y = ( ( y * 10 ) + ( b[i] - '0') ) % (MOD); // gave wrong answer

谁能澄清和解释它背后的数学原理？

Sample Test Case :
INPUT :
5
3 2
4 5
7 4
34534985349875439875439875349875 93475349759384754395743975349573495
34543987529435983745230948023948 3498573497543987543985743989120393097595572309482304

OUTPUT : 
9
1024
2401
735851262
985546465 

Answer 1

根据Fermat's little theorem的泛化,

a^b mod p = a^{b mod (p-1)} mod p