在做某道 CF\rm CFCF 题时,要用到这样的式子:
a×b mod pa\times b \bmod pa×bmodp
其中 a,b,p≤1018a,b,p\le 10^{18}a,b,p≤1018 。
然而写 O(logN)\mathcal O(\log N)O(logN) 的龟速乘,被卡常了(
去网上抄了一下用了 long double\text{long double}long double 的快速乘,然后被卡精度了(试过了不少人的模板,包括用了 eps\text{eps}eps 的,也被卡精度了)
然后似乎 CF\rm CFCF 不能用 __int128\verb!__int128!__int128 (当然也许是我太菜了没发现)
虽然最后还是用龟速乘勉强卡过去了,但还是想问一下,有没有什么能够快速处理 101810^{18}1018 量级的快速乘(网上好多都只能处理 101210^{12}1012 量级的)。