相关的数学原理直接链接
直接上一个模板代码
ll cal(int x,ll y,int mod) //计算和返回 y的x次方 % mod 的结果值
{
ll re=1; //结果值初始化
while(x) //分析次幂 x 的每一个二进制位
{
if(x&1) re=(re*y)%mod; //若当前位为 1，则累乘当前位的权并取模
x>>=1;
y=(y*y)%mod; //次幂 x 右移一位，计算该位的权后取模
}
return re; //返回结果值
}
OK
原文：https://www.cnblogs.com/savennist/p/13411921.html