安装网站模版视频教程,手机网站大全下载,前端做任务的网站,多用户商城网站开发对于a∗xb∗yca*xb*yca∗xb∗yc,这样一个二元一次方程组#xff0c;我们想要得到他的一组解可以用扩展欧几里得算法#xff0c;参数列表的a,b,x,y就是方程中的a,b,x,y#xff0c;d计算出来是gcd(a,b)。
算法求出来的是a∗xb∗ygcd(a,ba*xb*ygcd(a,ba∗xb∗ygcd(a,b的一组解…对于a∗xb∗yca*xb*yca∗xb∗yc,这样一个二元一次方程组我们想要得到他的一组解可以用扩展欧几里得算法参数列表的a,b,x,y就是方程中的a,b,x,yd计算出来是gcd(a,b)。
算法求出来的是a∗xb∗ygcd(a,ba*xb*ygcd(a,ba∗xb∗ygcd(a,b的一组解解系可以表示为Xxb/d∗k,Yy−a/d∗kXxb/d*k,Yy-a/d*kXxb/d∗k,Yy−a/d∗kk为任意整数
但是我们要求解的是a∗xb∗yca*xb*yca∗xb∗yc
方程组有解的充分必要条件是d∣cd|cd∣c正确性很容易证明
在确定方程组优解以后c/d∗X,c/d∗Yc/d*X,c/d*Yc/d∗X,c/d∗Y为方程组的一组解系
需要注意的是这样得到的不是方程组的所有的解
例如对于方程3xy603xy603xy60,17∗39∗16017*39*16017∗39∗160显然为一组解但是我们却没有办法用过扩展欧几里得算法得到这组解。所以凡是对x,y有限制条件不是指正负而是要求和不能超过多少等条件我们要考虑是否能够使用扩展欧几里得算法相反如果对x,y具体大小没有过多限制而是仅仅说明要求正负等条件时就可以使用扩展欧几里得算法。
void ex_gcd(ll a,ll b,ll d,ll x,ll y)
{if(!b){da; x1; y0;}else {gcd(b,a%b,d,y,x); y-x*(a/b);}
}下面简单证明一下正确性。
令ca%ba-k*b (ka/b) a∗x1b∗x2gcd(a,b)a*x1b*x2gcd(a,b)a∗x1b∗x2gcd(a,b) b∗x2c∗y2gcd(b,c)b*x2c*y2gcd(b,c)b∗x2c∗y2gcd(b,c) 有最大公因数的性质我们知道gcd(a,b)gcd(b,c)gcd(a,b)gcd(b,c)gcd(a,b)gcd(b,c) 所以我们得到等式a∗x1b∗y1b∗x2c∗y2b∗x2a∗y2−k∗b∗y2a*x1b*y1b*x2c*y2b*x2a*y2-k*b*y2a∗x1b∗y1b∗x2c∗y2b∗x2a∗y2−k∗b∗y2 其中的一组解为x1y2,y1x2−k∗y2,其中ka/bx1y2,y1x2-k*y2,其中ka/bx1y2,y1x2−k∗y2,其中ka/b因此我们可以递归的求解终止递归的条件为c0则这个时候的b为gcd(a,b)解为x1,y0然后递归的返回这个时候再看代码应该就能理解了代码实现很巧妙
为了快速得到非负的X,可以稍微处理一下X(X%B’B’)%B’这样得到的就应该是最小的非负X了 B’B/D
简单的例题hihoCoder#1297
#includecstdio
#includecstring
#includecstdlib
#includealgorithm
#includeiostream
#includecmath
#includectime
#includeclimits
#includequeue
#includevector
#includeset
#includemap
using namespace std;typedef long long ll;
const int INF0x3f3f3f3f;
const int MAXN1e55;ll s1,s2,v1,v2,m;void ex_gcd(ll A,ll B,ll D,ll x,ll y)
{if(!B){DA; x1; y0;}else{ex_gcd(B,A%B,D,y,x);y-(A/B)*x;}}int main()
{while(~scanf(%lld%lld%lld%lld%lld,s1,s2,v1,v2,m)){ll Av1-v2,Bm,Cs2-s1,D,x,y;if(A0){A-A; C-C;}C(C%mm)%m;ex_gcd(A,B,D,x,y);if(C%D){printf(-1\n);continue;}B/D;xC/D*x;x(x%BB)%B;printf(%lld\n,x);}return 0;
}
