洛谷P1226 快速幂

洛谷P1226 快速幂 传送门

这道题最暴力的写法是while循环p，但是当p大的时候就会TLE。然后就了解到了快速幂。

快速幂：顾名思义，快速幂就是快速算底数的n次幂。其时间复杂度为 O(log₂N)， 与朴素的O(N)相比效率有了极大的提高。

---

不得不说，二进制是一个很神奇的东西

• 任何一个正整数都能转换为二进制数（废话）

• 任何一个正整数都可以用几个 2 的幂次方的和表示。例如7，可转换为2⁰+2¹+2²，17可转换为2⁰+2⁴

---

该性质在二进制枚举中已经有所体现，那么在快速幂中有什么作用呢？

我们都知道 2ⁿ·2^m=2^n+m，那么联系到上述的二进制性质，我们就可以得到2ⁿ=2^a·2^b·…·2^m(a+b+…+m=n)，这和之前的2ⁿ=2¹·2¹·…·2¹(n个1)相比，（从O(n)优化到O(log n)） 显然快了很多。

另外&的应用（在二进制枚举中也有体现、转载）

关于 b & 1：
“&”美名曰“按位与”。
x & y 是二进制 x 和 y 的每一位分别进行“与运算”的结果。
与运算，即两者都为 1 时才会返回 1，否则返回 0。

          二进制
b     =    1011
1     =    0001
b&1   =    0001

因为 1（二进制）的前面几位全部都是 0，
所以只有 b 二进制最后一位是 1 时，b & 1 才会返回 1。
挺巧妙的，并且很快。)

---

快速幂模板（来自zj学长）：

ll quick(ll a, ll b, ll c)
{
   ll res = 1;
   while (b)
   {
       if (b & 1)
           res = (res * a) % c;
       a = (a * a) % c;
       b >>= 1;
   }
   return res % c;
}
int main()
{
   ll a, b, c;
   cin >> a >> b >> c;
   cout << a << '^' << b << ' ' << "mod" << ' ' << c << '=' << quick(a, b, c) << endl;
}