【模板】快速幂

今天学矩阵快速幂

那就先回忆一下我们最初认识的快速幂吧qvq

洛谷P1126 //这是一道只有七个测试点的神奇的题qwq

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 long long b,p,k,ans = 1;
 5 int main() {
 6     scanf("%lld%lld%lld",&b,&p,&k);
 7     long long a = b, q = p;
 8     while(q>0) {
 9         if(q&1) ans = ans*a%k;//指数为奇数时 
10         a = a*a%k;// 边乘边%  
11         q = q>>1;//指数减半 位运算 
12     }
13     ans %= k;//记得最后也要%一下k呀 不然 1^0 mod 1会输出1 QAQ 
14     printf("%lld^%lld mod %lld=%lld",b,p,k,ans);
15     return 0; 
16 }

总之岁月漫长，然而值得期待。