我们不妨先来看一道例题了解一下快速幂：
【模板】快速幂
A template.
观察到数据，\(a,b\le 2^{31}\)，普通的乘法是肯定不行的。
因此考虑优化：快速幂。
什么是快速幂？
顾名思义，就是快速地求出幂（\(a^b\)）。
怎么快速地求出幂？
将 \(a^b\) 展开，可得：
\[a^b = \underbrace{a\times a\times a\ldots\times a}_{b} \]下面的 \(b\) 表示个数啦。
然后将相邻两项合并，得到：
\[a^b = \underbrace{a^2\times a^2\times a^2\ldots\times a^2}_{\frac{b}{2}} \]这是会消除 \(\frac{b}{2}\) 个 \(a\)，因此还有 \(\frac{b}{2}\) 个 \(a\)。
但是 \(b\) 可能是奇数，所以需要额外乘一个 \(a\)，得到：
\[a^b = a\times \underbrace{a^2\times a^2\times a^2\ldots\times a^2}_{\frac{b}{2}} \]因此，每次操作都会让 \(b\to \frac{b}{2}\)，所以时间复杂度为 \(\mathcal O(\log{b})\)，足以通过此题。
如果说 \(b\le 10^{10000}\)，那就没办法了，得用更高深的算法（本蒟蒻也不会，qwq）。
代码实现
喜欢用函数的，可以定个 \(quickpow(a,b)\)。
-
特判 \(a=0\) 的情况，直接返回 \(0\)。
- 其实还有一种情况，就是 \(b=0\)，但是任何数的 \(0\) 次方都等于 \(1\)，因此不用顾虑。
-
当 \(n > 0\) 才做，用一个
while()循环。-
如果 \(n\bmod 2 =1\)（是奇数），那么 \(ans\) 处理多下的一个 \(a\)，也就是 \(ans\gets ans\times a\)。
-
然后 \(a\gets a^2\)，\(b\gets \frac{b}{2}\)，这就不用解释了吧。
-
-
最后返回 \(ans\) 即可。
code
#define ll long long
inline ll quick_pow(ll a,ll b) {
if(!a) return 0;
ll ans=1;
while(b){
if(b&1)//位运算优化。
ans=ans*a;
a=a*a;
b>>=1;//位运算优化 * 2。
}
return ans;
}
但这样并不能通过此题，因为 \(a^b\) 很有可能溢出。
那么就在上面的代码取模一下就行啦：
$\boxed{AC\ code}\ \ $局部
#define ll long long
inline ll quick_pow(ll a,ll b,ll p) {
if(!a) return 0;
ll ans=1;
while(b){
if(b&1) ans=ans*a%p;
a=a*a%p;
b>>=1;
}
return ans;
}
P10035 「FAOI-R2」Paint (A)
首先打出模拟代码找规律（别的大佬都是证明，就我找规律）。
i 从 1~10 的 answer：
1
4
13
40
121
364
1093
3280
9841
29524
咦，奇怪了，这好像哪里见过，不就是小学奥数的一道经典找规律吗？
递推公式：\(f_i = f_{i-1} \times 3+1\)；
通项公式：\(f_i = (3^i - 1)\div 2\)。
求 \(3^i\) 次方不就是快速幂吗？
但是除法没有同余性质，所以需要求逆元。 不知道逆元的，建议去这里。
代码就简单了：
ll quick_pow(ll x,ll p){//快速幂模板。
ll res=x,ans=1;
while(p){
if(p&1) ans=ans*res%MOD;
res=res*res%MOD;
p>>=1;
}
return ans;
}
int main(){
cin>>T;
sum=quick_pow(2,MOD-2);//求逆元。
while(T--){
cin>>n;
ssum=quick_pow(3,n);
ssum=(ssum-1+MOD)%MOD;
cout<<ssum*sum%MOD<<endl;
}
return 0;
}
但好像费马小定理有一个条件，不过似乎数据都是 $\gcd(a,p) =1 $(doge。
好啦，就到这里吧。
标签：frac,ll,笔记,times,学习,ans,quick,return,快速 From： https://www.cnblogs.com/2021zjhs005/p/18014134