【算法】875.快速幂

题目

875. 快速幂

思路

快速幂用于求解a的k次幂%p，时间复杂度更低。

代码 #include<iostream> using namespace std; typedef long long LL; int n; int qmi(int a, int k, int p) { int res = 1; while (k) { if (k & 1) { res = (LL)res * a % p; } k >>= 1; a = (LL)a * a % p; } return res; } int main() { cin >> n; while (n--) { int a, k, p; cin >> a >> k >> p; cout << qmi(a, k, p) << endl; } return 0; }