在模数为0或1的时候,会出现一些奇怪的结果。
inline int gcd(int a,int b){ if(b==0) return a; else{ while(int i=a%b){ a=b; b=i; } return b; }}int ex_gcd(int a,int b,int& x,int& y) { if(b==0) { x=1; y=0; return a; } int d=ex_gcd(b,a%b,x,y); int temp=x; x=y; y=temp-a/b*y; return d;}//解线性同余方程 ax + by = cbool _LCE(int a, int b, int c, int &x0, int &y0) { int x,y; int d=ex_gcd(a,b,x,y); if(c%d!=0){ //无解 return 0; } //ax0 + by0 = gcd(a,b) int k=c/d; x0=x*k; y0=y*k; //(x0,y0)是一组解 //x=x0+bt,y=y0+at,是方程的所有解,对所有整数t成立 return 1;}//解线性同余方程 ax = b mod n//这个是和 ax + ny = b 等价,注意变量int LCE(int a,int b,int n){ //printf("%d*x = %d mod %d\n",a,b,n); int x,y; if(_LCE(a,n,b,x,y)){ int t=n/gcd(a,n); //x0是最小非负整数解 //x=x0+k*t,对任意整数k都是解 int x0=(x%t+t)%t; return x0; } else{ //无解 return -1; }}