模线性方程（组）

2019-04-13 14:25发布

站内文章 / 模拟电子
10108 0 1108
ACM模版

公共部分（扩展GCD）

int extgcd(int a, int b, int &x, int &y) { if (b == 0) { x = 1; y = 0; return a; } int d = extgcd(b, a % b, x, y); int t = x; x = y; y = t - a / b * y; return d; }

模线性方程

/* * 模线性方程 a * x = b (% n) */ void modeq(int a, int b, int n) { int e, i, d, x, y; d = extgcd(b, a % b, x, y); if (b % d > 0) { cout << "No answer! "; } else { e = (x * (b / d)) % n; for (i = 0; i < d; i++) { cout << i + 1 << "-th ans:" << (e + i * (n / d)) % n << ' '; } } return ; }

模线性方程组（互质）

/* * 模线性方程组 * a = B[1](% W[1]); a = B[2](% W[2]); ... a = B[k](% W[k]); * 其中W，B已知，W[i] > 0且W[i]与W[j]互质，求a（中国剩余定理） */ int china(int b[], int w[], int k) { int i, d, x, y, m, a = 0, n = 1; for (i = 0; i < k; i++) { n *= w[i]; // 注意不能overflow } for (i = 0; i < k; i++) { m = n / w[i]; d = extgcd(w[i], m, x, y); a = (a + y * m * b[i]) % n; } if (a > 0) { return a; } else { return (a + n); } }

模线性方程组（不要求互质）

typedef long long ll; const int MAXN = 11; int n, m; int a[MAXN], b[MAXN]; int main(int argc, const char * argv[]) { int T; cin >> T; while (T--) { cin >> n >> m; for (int i = 0; i < m; i++) { cin >> a[i]; } for (int i = 0; i < m; i++) { cin >> b[i]; } ll ax = a[0], bx = b[0], x, y; int flag = 0; for (int i = 1; i < m; i++) { ll d = extgcd(ax, a[i], x, y); if ((b[i] - bx) % d != 0) { flag = 1; // 无整数解 break; } ll tmp = a[i] / d; x = x * (b[i] - bx) / d; // 约分 x = (x % tmp + tmp) % tmp; bx = bx + ax * x; ax = ax * tmp; // ax = ax * a[i] / d } if (flag == 1 || n < bx) { puts("0"); } else { ll ans = (n - bx) / ax + 1; if (bx == 0) { ans--; } printf("%lld ", ans); } } return 0; }

热门文章