class="markdown_views prism-atom-one-light">

简介

xymodp
当y很大的时候，怎么办？

方法

这里只讲当x与p互质时的情况。
所以x%p与p互质，那么就相当于x与p互质，就相当于p是个质数，所以根据欧拉定理
xφ(p)≡1(modp)
所以xy就可以拆解成
xφ(p)+φ(p)+......+φ(p)+(ymodφ(p))modp=x0+0+......+0+(ymodφ(p))modp
所以得出结论
xymodp=xymodφ(p)modp(当p是质数)