4-快速幂

算法思想

1. 拆分指数
   1. 将指数表示为二进制的形式
   2. 运用幂运算的性质，拆分指数

算法模板

public static long qmi(long a, int b, int p) 
{
	long res = 1;
	while(b > 0)
	{
		// 取二进制形式下的 b 的最后一位数
		int last = b >> 0 & 1;
		if(last > 0) res = (res * a) % p;
		a = a * a % p;
		b >>= 1;
	}
	return res;
}

参考资料

1. 快速幂 - OI Wiki