算法题（159）：快速幂

审题：
本题需要我们计算出(a^b)%c的值，并按照规定格式输出

思路：
方法一：暴力解法

我们直接循环b次计算出a^b,然后再取余c，从而得出最终结果

时间上：会进行2^31次，他的数量级非常大，一定会超时

空间上：由于a和b的最大值都是2^31，所以最终的结果也是大于longlong类型的，会溢出结果

综上，暴力解法的时间和空间都无法通过，我们无法采用该方法

方法二：快速幂

快速幂是基于倍增思想的，接下来我们看看倍增思想是如何体现出来的

我们可以通过每次倍增a的n次方来快速得到a的2的n次幂的结果，而不需要一个个a乘，大大减少了a的次方的计算时间。

但是这也有个问题，就是我们只能知道a的2的n次幂，而无法知道其他的结果

（比如a^11），那么我们如何去求出其他结果？

经过观察我们发现，其实我们计算出的a的2的n次幂其实是二进制的权值

这里我们以a^11为例子，先将11从十进制转为二进制的值1011.

然后将他根据二进制的含义拆解为2的n次幂的式子，此时我们就可以利用上我们倍增计算出来的数据表示出任意次方的a的值了

那么此时时间的问题就解决了，可是计算的时候仍然会出现数据溢出的情况，空间问题如何解决？

性质1：如果只涉及加法，乘法的取模运算，我们可以在任意地方取模

性质2：如果取余结果可能为负，而题目要求取余结果必须为正，那么我们有“模加模”的方法补正

由于a-b关于c取余了，所以结果的绝对值一定小于c，此时我们加c就会让中括号内的数据值大于0，这就是补正，然后我们再取余c即可

根据性质1我们可知：我们可以在计算倍增的同时对倍增的结果取余c，然后在计算answer的时候也取余c，这样子空间问题就解决了

解题步骤：
1.在倍增计算的之前对该倍增数据是否需要乘入answer进行判断

2.answer判断完之后倍增数据

3.b右移一位和&1操作结合，从而得知下一个倍增数据的选择情况

解题：
 

#include<iostream>
using namespace std;
typedef long long ll;
ll a, b, c;
ll func(ll a, ll b, ll c)
{ll answer = 1;while (b){if (b & 1)answer = answer * a % c;//与answer*=a%c不同a =a * a % c;//倍增b = b >> 1;}return answer;
}
int main()
{cin >> a >> b >> c;printf("%lld^%lld mod %lld=%lld", a, b, c, func(a,b,c));return 0;
}

1.格式化输出：由于本题的答案输出有特定格式，所以我们使用c语言的输出语句printf比较合适

2.我们需要根据b的二进制位来判断当前倍增数据是否需要乘进answer，为1时需要，为0时不需要，所以我们使用b&1来判断当前位是否为1

3.在计算倍增和answer的时候都取模c，从而满足空间需求

4.不要省略的写计算式，因为answer*=a%c和answer = answer * a % c是不同的

P1226 【模板】快速幂 - 洛谷