一只蒟蒻的龟速乘学习笔记
背景
关于快速幂:
它死了。
咳咳。
以下是快速幂模板:
1 | inline int q_p(int a, int k, int p) |
可以看出,快速幂有一个缺点:当模数 p 大于 int 范围(最大值为
此时解决
于是,龟速乘应运而生。
龟速乘
原理
通过将 乘法 转化为 加法并每次取模 而避免了爆 long long。
代码
1 | //龟速乘 |
速度
顾名思义,龟速乘会比系统的乘法慢一些。
OK就这样。
本蒟蒻新学 OI ,如有错误请 D 我。
关于快速幂:
它死了。
咳咳。
以下是快速幂模板:
1 | inline int q_p(int a, int k, int p) |
通过将 乘法 转化为 加法并每次取模 而避免了爆 long long。
1 | //龟速乘 |
顾名思义,龟速乘会比系统的乘法慢一些。
OK就这样。
本蒟蒻新学 OI ,如有错误请 D 我。