这几天讲的倍增捏(一开始以优化 dp 为主,现在几乎纯倍增,6)。然后发现我不会快速幂。
Luogu P1226.【模板】快速幂||取余运算 传送门
我们知道任意整数可以表示成若干个 2 的次幂项的和。现在要求一个数的幂,那么我们可以将所需要求的幂转化为 2 的次幂项之和,即转化为二进制来计算。每次判断这个位置的二进制是 1 还是 0,进行相应的乘法计算。数学不好,直观的看一眼时间复杂度效率的差异:暴力做法是 log(n) 的,快速幂算法是 log2n 的,速度一下快了很多。
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include<bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 ll ans = 1; 5 ll a, b, p; 6 ll aa, bb, mod; 7 int main() 8 { 9 scanf("%lld%lld%lld", &a, &b, &p); 10 aa = a; 11 bb = b; 12 mod = p; 13 while(b) 14 { 15 if(b % 2) ans = ans * a % p; 16 a = a * a % p; 17 b /= 2; 18 } 19 printf("%lld", ans % p); 20 return 0; 21 }快速幂模板
最后记得输出之前再取模一次,一开始被你校 oj 上的数据卡住了:123456789 0 1。(多组数据别忘了清空,不开 long long 见祖宗。)
标签:10,ll,long,2023.3,ans,mod,lld From: https://www.cnblogs.com/Moyyer-my/p/17204504.html