求助 O(1) 快速乘
  • 板块学术版
  • 楼主囧仙
  • 当前回复16
  • 已保存回复16
  • 发布时间2020/8/31 20:54
  • 上次更新2023/11/5 13:52:14
查看原帖
求助 O(1) 快速乘
330759
囧仙楼主2020/8/31 20:54

在做某道 CF\rm CF 题时,要用到这样的式子:

a×bmodpa\times b \bmod p

其中 a,b,p1018a,b,p\le 10^{18}

然而写 O(logN)\mathcal O(\log N) 的龟速乘,被卡常了(

去网上抄了一下用了 long double\text{long double} 的快速乘,然后被卡精度了(试过了不少人的模板,包括用了 eps\text{eps} 的,也被卡精度了)

然后似乎 CF\rm CF 不能用 __int128\verb!__int128! (当然也许是我太菜了没发现)

虽然最后还是用龟速乘勉强卡过去了,但还是想问一下,有没有什么能够快速处理 101810^{18} 量级的快速乘(网上好多都只能处理 101210^{12} 量级的)。

2020/8/31 20:54
加载中...