有魅力天空

文章
3
资源
0
加入时间
2年10月21天

【带模的除法】poi2008 per

<br />这道题的难点在于带模的除法,可恶的是模还不是质数,更可恶的是还没办法约分。。<br /> <br />看了标程才知道原来还可以这样做:<br />把取模的数进行分解质因数,对于你要乘或者要除以某一个数的时候,将这个数和模的gcd额外处理(其实直接把质因数的几次幂记下来就可以了),对于不是gcd的部分直接乘法逆元即可。<br /> <br />我是参考的标程的写法(ps:标程跑得非常慢),加略微的改进,感觉我应该不