n元一次不定方程 模板

设方程a1x1 + a2x2 + a3x3 + a4x4 = c，所有系数的最大公因数应该整除c。将方程转换为方程组递归求解， a1x1 + a2x2 = d2t2, d2t2 + a3x3 = d3t3, d3t3 + a4x4 = c.逐级替换。求出来的解有正有负，系数也可以为负，返回false表示没有整数解。 int gcd(int a, int b){ return (b==0) ? a : gcd(b,a%b); } int e_gcd(int a, int b, int& x, int& y){ if(b == 0){ x = 1; y = 0; return a; } int ans = e_gcd(b, a%b, y, x); y -= x*(a/b); return ans; } //index start from 1,x,y maybe negative bool n_equation(int a[], int x[], int c, int n){ vector<int> d(n+3); d[1] = a[1]; for(int i = 2; i < n; ++i) d[i] = gcd(a[i-1],a[i]); if(c%d[n-1] != 0) return false; int y,gcdd; for(int i = n-1; i >= 1; --i){ gcdd = e_gcd(a[i+1],d[i],x[i+1],y); x[i+1] *= c/gcdd; y *= c/gcdd; c = d[i] * y; } x[1] = y; return true; }