使用⑨进制优化龟速乘()

我们都知道在计算 \(a\times b \bmod p\) 的时候,如果 \(a,b,p\) 的范围都是 \(10^{18}\),那么直接计算会溢出

有一种经典的方法是把 \(b\) 做二进制拆分,但是这样的话需要做 \(O(\log_2 b)\) 次加法,导致时间复杂度乘上一个 \(60\) 之类的常数

我们发现这种题一般会把 \(p\) 出到 \(10^{18}\),但是 \(\texttt{long long}\) 实际上的范围可以到 \(2^{63}-1>9\times 10^{18}\)

所以其实我们可以使用⑨进制来优化,做到 \(\log_9 b\)

使用这个优化来写 \(\text{Miller-Rabin}\) 算法,发现比二进制的龟速乘快了三倍多

  • 二进制龟速乘
  • ⑨进制龟速乘

貌似八进制可以使用位运算优化,会不会更快呢

然而并没有更快,甚至开 Ofast 也比⑨进制慢一点,但是事实就是这样,小编也感到非常惊讶。

这就是关于使用⑨进制优化龟速乘的事情了,大家有什么想法呢,欢迎在评论区告诉小编一起讨论哦!

————————

我们都知道在计算 \(a\times b \bmod p\) 的时候,如果 \(a,b,p\) 的范围都是 \(10^{18}\),那么直接计算会溢出

有一种经典的方法是把 \(b\) 做二进制拆分,但是这样的话需要做 \(O(\log_2 b)\) 次加法,导致时间复杂度乘上一个 \(60\) 之类的常数

我们发现这种题一般会把 \(p\) 出到 \(10^{18}\),但是 \(\texttt{long long}\) 实际上的范围可以到 \(2^{63}-1>9\times 10^{18}\)

所以其实我们可以使用⑨进制来优化,做到 \(\log_9 b\)

使用这个优化来写 \(\text{Miller-Rabin}\) 算法,发现比二进制的龟速乘快了三倍多

  • 二进制龟速乘
  • ⑨进制龟速乘

貌似八进制可以使用位运算优化,会不会更快呢

然而并没有更快,甚至开 Ofast 也比⑨进制慢一点,但是事实就是这样,小编也感到非常惊讶。

这就是关于使用⑨进制优化龟速乘的事情了,大家有什么想法呢,欢迎在评论区告诉小编一起讨论哦!