前题引入
我们平时用的pow函数速度太慢了怎么办，我就就需要快速幂（意思废话）
题目分析
前题铺垫
你只是需要知道一个非常简单的东西
a^b + a^c =a^(b+c)
思路
既然暴力是O(b)的，那我们是不是可以考虑O(log b)
那我们尝试将b除以2
那么就可以知道a^b = a^b/2 + a^b/2
但是我们可以想到如果b是个单数怎么办呢，因为c++是默认向下取整的，所以 a^b = a^b/2 + a^b/2 +a^b%2
代码（模板）
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a,b,mod;
int qpow(int a,int b){if(b==1) return a;else if(b==0) return 1;else{int ans=qpow(a,b/2)%mod;int ans1=(ans%mod)*(ans%mod)%mod;if(b%2==1){ans1=((ans1%mod)*(a%mod))%mod;} return ans1%mod;}
}
signed main(){cin>>a>>b>>mod;cout<<a<<"^"<<b<<" mod "<<mod<<"="<<qpow(a,b)%mod;return 0;
}