【模板】快速幂

（还记得大明湖畔的快速幂吗？）

先提一个小问题，怎么求a的n次方？

当然是暴力。。直接乘就好啊。。

等等，当n=10e+9怎么办？（当然我知道这玩意一般还要再模一个c）

难不成你还想。。（不你不想）

这时，蒟蒻默默打出一个问号。。（所以我去学了快速幂）

————快速幂

原理：

首先，有这样一个公式

（a*b）%c=（（a%c）*（b%c））%c;

（a^b）%c=（（a%c）^b）%c

长得好奇怪。。但其实和实数运算法则一样。。

这样就有下面的第一步优化，为了使求出来的值不超long long 

int ans = 1;
a = a % c;  //加上这一句
for(int i = 1;i<=b;i++)ans = ans * a;
ans = ans % c;

（但是这样也还是会超。。）

再看一下上面的公式，既然先相乘再取余与先取余再相乘再取余一样，那就可以给每一步的结果ans取余。

int ans = 1;
a = a % c;
for(int i = 1;i<=b;i++)ans = (ans * a) % c;//这里再取了一次余
ans = ans % c;

这时的时间复杂度为O（b）

虽然现在不会溢出，但是当b很大的时候还是会超时

然后，有这样一个公式

a^b%c==((a^2)b/2)%c == ((a^2 % c)b/2)%c          b为偶数

a^b%c==(a*(a^2)b/2)%c == (a*(a^2 % c)b/2)%c         b为奇数

这样，就可以进一步优化为：

int ans = 1;
a = a % c;
k = (a*a) % c;               //相当于用k代替了a2
if(b%2==1)
    ans = (ans * a) % c; //如果是奇数，要多求一步，可以提前算到ans中
for(int i = 1;i<=b/2;i++) ans = (ans * k) % c;
ans = ans % c;

这时的时间复杂度是O（b/2）

还是远远不够啊。。

但是，由上面的一次优化可以发现，我们已经把a^b%c转换成了k^(b/2)%c

而K^(b/2)%c是可以继续迭代下去的

例如，

下一步再令 x=(k*k)%c 偶数就是求 x^b/4 % c 奇数就是 (x^b/4 % c*a)% c

再下一步令 y=(x*x)%c 偶数就是求 y^b/8 % c 奇数就是 (y^b/8 % c*a)% c

    ......  直到指数b ==0

当然，对于奇数的情形会多出一项a % c，所以为了完成迭代，当b是奇数时，我们通过ans = (ans * a) % c; 来弥补多出来的这一项

int ans = 1;
a = a % c;
while(b>0)
{
      if(b % 2 == 1)ans = (ans * a) % c;   //奇数，补一项
      b = b/2;
      a = (a * a) % c;
}
cout<<ans<<endl;

这时的时间复杂度是O(logb)

就是完整的快速幂算法！

#include<iostream>
#include<cstdio>
using namespace std;
long long int a,b,c;
long long int ans=1,bent;
int main()
{
    scanf("%d%d%d",&a,&b,&c);
    bent=a;
    while(b)
    {
        if(b&1)
        ans=(ans*bent)%c;
        bent=(bent*bent)%c;
        b/=2;
    }
    printf("%d",ans);
    return 0;
}

看一道题吧。。这个是裸的快速幂（点击收获RP）先把板子打会吧。。

（RP++！）