洛谷 P1226 快速幂

题目链接：快速幂

思路

       简单快速幂模板。a ^ 17 = (a ^ 2) ^ 8 * a，此时pow()中的y就可以视为17 -> 8（y >>= 1），pow()中的x就是底数a -> a ^ 2（x *= x），结果res可以视为在循环时多出来的后边乘的a，1 -> a（res *= x），简单代数推导就会发现y = 1的时候，会有res *= x此时的x为a ^ 16，则返回的res就是2 ^ 17。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
#define ll long long

ll pow(ll x, ll y, ll p) {
  ll res = 1;
  while (y) {
    if (y % 2) {
      res *= x;
      res %= p;
    }
    y >>= 1;
    x *= x;
    x %= p;
  }
  return res;
}

int main() {
  ll a, b, p;
  cin >> a >> b >> p;

  cout << a << "^" << b << " mod " << p << "=" << pow(a, b, p);
  return 0;
}