最近发现快速幂真的很好用（太长时间没用都快忘了） 题目背景如下: P1226 【模板】快速幂 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

【模板】快速幂

题目描述

给你三个整数 $a,b,p$，求 $a^b \bmod p$。

输入格式

输入只有一行三个整数，分别代表 $a,b,p$。

输出格式

输出一行一个字符串 a^b mod p=s，其中 $a,b,p$ 分别为题目给定的值， $s$ 为运算结果。

样例 #1

样例输入 #1

2 10 9

样例输出 #1

2^10 mod 9=7

提示

样例解释

$2^{10} = 1024$，$1024 \bmod 9 = 7$。

数据规模与约定

对于 $100\%$ 的数据，保证 $0\le a,b < 2^{31}$，$a+b>0$，$2 \leq p \lt 2^{31}$。

对于这样的一个问题，我们要求a^b暴力相乘的话

for(int i=1;i<=b;i++)
{
     int ans=1;
     ans=ans*a;
}

那这样的话就需要计算b次，时间复杂度是O(b)级别的， 这样算就很慢，那我们用快速幂做的话时间复杂度就是O(log b)级别的 那至于怎么实现快速幂，请看下面的代码

---

---

---

先补充两个知识：按位与&，位运算

按位与&

就是将两个二进制数每一位进行与的逻辑操作，规则：有0即0

eg.（1110）2&（0100）2=（0100）2=4

位运算（"<<"和">>")

">>"就是右移符号，它是将整个数的二进制表示向右移n位，空位自动补零。

比如p>>1就是p的二进制表示向右移一位。

"<<"就是左移符号，它是将整个数的二进制表示向左移n位，空位自动补零。

比如p<<1就是p的二进制表示向左移一位。 那么这是二进制下的，反映到十进制下">>"表示除以2 "<<"表示乘以2 eg. 32>>2=32/(2^2)=8 2<<3=2*(2^3)=16 那么接下来就是写代码的时候了！

int ksm(int a, int b)
{
      int ans = 1;
      while(b)//<=>while(b!=0)
      {
            if(b&1)//如果n的当前末位为1
           {       
                    ans *= a; //ans乘上当前的a
                    
           }
           a *= a;  //a自乘                   
           b>>= 1;  //n往右移一位
      }
       return ans;
     //O(logb)
}

原理就是将b变为二进制，然后二进制的每一位跟1比一下，如果是1就算进去，不是就不算比如算a的5次方，5=（101）2,那么就算有1的那一位即（101）2中的第一个1和第三个1，然后算到ans里面，（101）2往右移1位变成（10）2，依此类推，最后返回ans就是幂后的值

---

---

---

那现在回到这个题中，我们怎么解决这个有模数的题呢？ AC代码如下

#include<bits/stdc++.h>
typedef long long ll;
int ksm(ll a,ll b,ll k)//定义快速幂函数
{
    ll ans=1;
    while(b)//<=>while(b!=0)
    {
        if(b&1) //如果是1
        {
             ans=ans*a%k;
        }
        a=a*a%k;
        b>>=1;
    }
    return ans;
}
int main()
{
    ll a,b,k;
    ll c;
    std::cin>>a>>b>>k;
    c=ksm(a,b,k);
    std::cout<<a<<"^"<<b<<" mod "<<k<<"="<<c;
    return 0;
}//温馨提示：看数据范围开long long