2018 蓝桥杯省赛 B 组模拟赛(五)—— 快速幂
一个数的整数次幂,是我们在计算中经常用到的,但是怎么可以在
\mathcal{O}(\log (n))O(log(n)) 的时间内算出结果呢?代码框中的代码是一种实现,请分析并填写缺失的代码,求 x^y \mod pxymodp 的结果。
答案: pw(x,y / 2, p) * pw(x, y / 2, p) % p
一个数的整数次幂,是我们在计算中经常用到的,但是怎么可以在
\mathcal{O}(\log (n))O(log(n)) 的时间内算出结果呢?代码框中的代码是一种实现,请分析并填写缺失的代码,求 x^y \mod pxymodp 的结果。
答案: pw(x,y / 2, p) * pw(x, y / 2, p) % p