求线性同余方程的所有解，下面给出代码如下
long long exgcd(long long a,long long b,long long &x,long long &y) { if(b==0) { x=1; y=0; return a; } long long ans=exgcd(b,a%b,x,y);///使ax+by=gcd(a,b)成立的一组解 long long temp=x; x=y; y=temp-a/b*y; return ans;/// 返回a，b的最大公因数 } int f(int a,int b,int m) { long long g=exgcd(a,m,x,y);///ax与b模m同余 if(b%d!=0) return -1; x=x*(b/g)%m; for(int i=1;i<=g;i++) ans[i]=(x+(i-1)*m/g)%m; }
下面给出求出此方程组小于m的非负整数解的代码
long long exgcd(long long a,long b,long long x,long long y) { if(b==0) { x=1; y=0; return a; } long long ans=exgcd(b,a%b,x,y); long long temp=x; x=y; y=temp-a/b*y; return ans; } int solve() { scanf("%lld%lld",&a1,&r1); for(int i=1;i<n;i++)///总共有n个方程 { scanf("%lld%lld",&a2,&r2); a=a1,b=a2,c=r2-r1; long long g=exgcd(a,b,x0,y0); if(c%g!=0) { ifhave=0; } int t=b/g; x0=(x0*(c/g)%t+t)%t; r1=a1*x0+r1; a1=a1*(a2/g); } if(ifhave==0) { r1=-1; } return r1; }