推荐一篇关于逆元的blog
里面也有大部分今天讲的知识>-<
除法定理
x=a*p+b，y=c*p+d；
x%p=b,y%p=d;
加减乘
x±y=(a±b)p+(c±d)，设c±d=e*p+f，那么
x±y=(a±b+e)p+f，所以(x±y)%p=(c±d)%p=((x%p)±(y%p))%p
x*y=(a*c)*p^2+(b*c+a*d)*p+(c*d)，设c*d=e*p+f
那么xy=(a*c*p+b*c+a*d+e)p+f，(xy)%p=(cd)%p=((x%p)(y%p)%p)
然而除法。。。
暴力除法不可取，因为除法不满足同余性质。
举个栗子；
8%7=1,2%7=2,(8/2)%7=4
((8%7)/(2%7))%7=excuse me?
减法和除法本质上是对加法和乘法的逆元做运算
听不懂的玄学逆元
xa+yb=d=gcd(a,b)=gcd(b,a)=gcd(a,b-a);
因为b不断减a，直到小于a，相当于是b%a；
gcd（a,b）=gcd(a,b%a);
一行gcd
int gcd(int a,int b) {return !b? a:gcd(b,a%b);}
gcd(a,b)时间复杂度（loga+logb）[最坏情况取在斐波那契数列两个相邻数上]
扩展欧几里德
欧拉定理
若x与p互余
因篇幅问题不能全部显示，请点此查看更多更全内容