欧几里得算法与扩展欧几里得算法
递归写法
gcd
int gcd(int a,int b) { return !a ? b : gcd(b%a,a); }
扩欧
struct value{ int x,y; value(int x,int y):x(x),y(y){} }; value ExtEuclid(int a,int b) { if(a==0) return value(0,1); value r=ExtEuclid(b%a,a); return value(r.y-b/a*r.x,r.x); }
非递归写法
gcd
int gcd(int a,int b) { while(a) b=b%a,swap(a,b); return b; }
扩欧的不会.....
求剩余系中某数的乘法逆元
考虑剩余系下的除法,a/b=ab-1(mod MOD) ,有a-1a=1(mod MOD),这个算法求出a-1 ........
注意只有模数为质数时,整个剩余系的除零以外其它元素才都会有逆元.
int getrev(int p) { return p==0 ? -1 : (ExtEuclid(p,MOD).x%MOD+MOD)%MOD; }
具体的,要求 ax≡1(mod MOD) ,有 ax+MODy=1. 如果a与MOD的gcd不为1,则逆元不存在.
直接用扩欧来算(x,y)就行了......
未完待续
中国剩余定理
模意义下的高斯消元
求原根
原文：http://www.cnblogs.com/DragoonKiller/p/4355855.html