主要问题是怎么求$a^b \ mod \ c$。

可以用欧拉定理降幂。

$$a^b \ mod \ c = a ^ {b \% \varphi(c) } \; mod \ c (b < \varphi(c))$$

$$a^b \ mod \ c = a ^ {b \% \varphi(c) + \varphi(c)} \; mod \ c (b \geqslant \varphi(c))$$

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5 char B[1000005], A[1000005]; 6 typedef long long ll; 7 ll phi(int x) { 8     ll res = x; 9     for (int i = 2; i * i <= x; ++i)10         if (x % i == 0) {11             res = res / i * (i - 1);12             while (x % i == 0) x /= i;13         }14     if (x > 1) res = res / x * (x - 1);15     return res;16 }17 ll pow(ll a, ll b, ll m) {18     ll res = 1;19     for (a %= m; b; b >>= 1, a = (a * a) % m)20         if (b & 1) res = (res * a) % m;21     return res;22 }23 int c;24 ll a, a_1, b;25 int main() {26     scanf("%s", A); scanf("%s", B); scanf("%d", &c);27     int lal = strlen(A), lbl = strlen(B);28     for (int i = 0; i < lal; ++i) {29         a = (a * 10 + A[i] - '0') % c;30     }31     for (int i = lal - 1; ~i; --i) {32         if (A[i] == '0') A[i] = '9';33         else {--A[i]; break;}34     }35     for (int i = 0; i < lal; ++i)36         a_1 = (a_1 * 10 + A[i] - '0') % c;37     int flag = 0, p = phi(c);38     for (int i = 0; i < lbl; ++i) {39         b = (b * 10 + B[i] - '0');40         if (b >= p) flag = 1;41         b %= p;42     }43     if (flag) b += p;44     ll ans = pow(a, b - 1, c) * a_1 % c;45     printf("%lld\n", ans ? ans : c);46     return 0;47 }