快速幂

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;                            //注意要用long long，用int会出错
ll fastPow(ll a, ll n,ll m){                     //a**n mod m
  if(n == 0) return 1;                           //特判 a0= 1
  if(n == 1) return a;
  ll temp = fastPow(a, n/2,m);                   //分治
  if(n%2 == 1) return temp * temp * a % m;       //奇数个a。也可以这样写： if(n &1)
  else return temp * temp % m ;                  //偶数个a
}
int main(){
  ll a,n,m; cin >> a >> n>> m;                   //底数、指数、取模
  cout << fastPow(a,n,m);
  return 0;
}

笔记：快速幂就是快速高效的算出幂，当指数很大时，暴力法算出的结果会超时，分治算法可以将大问题，划分成多个小问题解决。
取余：靠近0原则，取模：商取小原则