nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 让你用lg的时间复杂度求下面这东西(n<1e18) $$\begin{aligned}&\prod_{i=1…n}{(2i-1)} %2^{64}\&suppos...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253...

核心思想

蒙哥马利运算是一种新的运算，他把乘模简化为对进制数的除法，以及简单加法，这就使得乘模避开了大量的取模试除。

蒙哥马利表示法

例如$a%mod$的蒙哥马利表示法为$f(a) = a\times p% mod$，$p$是一个进制数， 我们储存$f(a)$的值，而不是a的值。

复原

于是我们很容易发现，对于蒙哥马利表示法变回普通表示法时只需要乘p对mod的逆元即可。

p的取值

蒙哥马利表示法会找一个进制数使得普通数字转化为蒙哥马利表示法，一般来说这是一个刚好大于模数的进制数。