小技

按位相乘

所谓的按位相乘,用在两个大数相乘取模。可能两个大数和取模的数都在类型内,但是乘起来可能就会爆类型。所以将其中一个大数表示成二进制,一位一位的与另一个大数相乘取模。其中利用迭代,时间复杂度在 O(log n)
下面是代码

 

二分快速幂

二分快速幂可以利用于满足结合律的运算,比如说求幂取模。原理是将一大段运算分为两端完全相同的运算,从而达到节约的效果。时间复杂度在 O(log n) ,下面给出快速幂求模的代码

 

持续更新

One thought on “小技

  1. Pingback: [CF621E]Wet Shark and Blocks | 火药

发表评论

电子邮件地址不会被公开。 必填项已用*标注