exCRT & 骆克强乘法
只是丢两个板子啦。
exCRT的做法就是每次拿两个方程合并成一个,合并的过程推下式子就是个 exgcd。具体可以在 zjk 的 ptt 里面找到。
先放个O(1)慢速乘
cpp
1 | ll mul( ll a , ll b , ll p ) { a %= p , b %= p; return ( (a * b - (ll)( (ll)( (long double)a / p * b + 0.5 ) * p )) % p + p ) % p; } |
然后一个 exgcd
cpp
1 | void exgcd( ll a , ll b , ll& d , ll& x , ll& y ) { |
最后是 excrt
Luogu 板子题和 PTT 上的 ab 居然是反着的。。。毒瘤
cpp
1 |
|