快速幂

快速幂 1.快速幂快速幂的核心：反复平方法 快速幂即快速的求出 $a^kmodp$ 的结果，可以在 $O(logk)$ 的时间复杂度内求出结果，其中满足 $1≤a,p,k≤10^9$， 12345//暴力法O(k)res = 1;for (int i = 1; i <= k; ++i) { res = res * a % p;} 12345678//快速幂O(logk)int res = 1;while (k) { if (k & 1) res = (long long)res * a % p; k >>= 1;//最后一位抹去 a = (long long)a * a % p;}return res; 1.AcWing875.快速幂123456789101112131415161718192021222324#include<iostream>using namespace std;//a^k % pint qmi(int a, int k, int p) { int res = 1; while (k) { if (k & 1) res = (long long)res * a % p; k >>= 1;//最后一位抹去 a = (long long)a * a % p; } return res;}int main() { int m; scanf("%d", &m); while (m--) { int a, k, p; scanf("%d%d%d", &a, &k, &p); printf("%d\n", qmi(a, k, p)); } return 0;} 2.AcWing876.快速幂求逆元 考察：费马定理与快速幂 1234567891011121314151617181920212223242526#incl ...