今天学矩阵快速幂
那就先回忆一下我们最初认识的快速幂吧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 }