扩展欧几里得最大最小正整数解

2019-04-14 16:13发布

站内文章 / 模拟电子
11749 0 1175
#include #include #include using namespace std; /* 解模方程ax=b(mod n) x的正整数解 等价于求ax+ny=b的x的正整数解 令d=gcd(a,n) 若d|b 则方程有解，否则无解. gcd的过程实际就是在求ax+ny=gcd(a,n)的过程 所以最后求出gcd后 x=1 y=0 */ int ex_gcd(int a,int b,int &x,int &y) { if(b==0) { y=0; x=1; return a; } int ans=ex_gcd(b,a%b,y,x); y-=a/b*x; return ans; } int main() { int a,b,n,x,y,d; scanf("%d%d%d",&a,&b,&n); d=ex_gcd(a,n,x,y); if(b%d==0) //有解 { /* 在 xi mod n的情况下: xi=x0+i(n/d)(i=1,2,…d). 特别的设e=x0+n，方程ax=b(mod n)的最小整数解x1=e mod (n/d),最大整数解x2=x1+(d-1)*(n/d)。 */ int e=x+n,t=1; for(int i=1;i<=d;i++) printf("x[%d]=%d ",i,(x+(n/d)*i)*t); int x1=e%(n/d)*t,x2=(x1+(d-1)*(n/d))*t;//最小正整数解为x1 最大正整数解为x2 printf("最小正整数解x1=%d 最大正整数解x2=%d ",x1,x2); } else cout<<"无解"<

热门文章