#include <iostream> #include <cstdio> #include <cstring> using namespace std; int pow_mod(int a, int n, int m) { //时间复杂度:O(logn) if(n == 1) { return a%m; } int x = pow_mod(a, n/2, m); long long ans = (long long)x * x % m; if(n%2 == 1) { ans = ans * a %m; } return (int)ans; } int mod(int a, int n, int m) { int ans = 1, i; for(i = 1; i <= n; i++) { ans = ans*a%m; } return ans; } long long quick_mod(long long a, long long b, long long m) { //时间复杂度:O(logn) long long ans = 1; while(b) { if(b&1) { ans = (ans*a)%m; b--; //我认为可以省略。 } b /= 2; a = a*a%m; } return ans; } int main() { int a, n, m; while(scanf("%d%d%d", &a, &n,&m) == 3) { int res1 = pow_mod(a, n, m); int res2 = mod(a, n, m); int res3 = quick_mod((long long)a, (long long)n, (long long)m); cout << "res1 = " << res1 << endl; cout << "res2 = " << res2 << endl; cout << "res3 = " << res3 << endl; } return 0; }