123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100 |
- // This is a collection of useful code for solving problems that
- // involve modular linear equations. Note that all of the
- // algorithms described here work on nonnegative integers.
- // return a % b (positive value)
- int mod(int a, int b) {
- return ((a%b)+b)%b;
- }
- // computes gcd(a,b)
- int gcd(int a, int b) {
- int tmp;
- while(b){a%=b; tmp=a; a=b; b=tmp;}
- return a;
- }
- // computes lcm(a,b)
- int lcm(int a, int b) {
- return a/gcd(a,b)*b;
- }
- // returns d = gcd(a,b); finds x,y such that d = ax + by,
- // with |x|+|y| minimal.
- int extended_euclid(int a, int b, int &x, int &y) {
- if (!b) { x = 1; y = 0; return a; }
- else { int d = extended_euclid(b, a%b, y, x); y -= x*(a/b); return d; }
- }
- // finds all solutions to ax = b (mod n)
- VI modular_linear_equation_solver(int a, int b, int n) {
- int x, y;
- VI solutions;
- int d = extended_euclid(a, n, x, y);
- if (!(b%d)) {
- x = mod (x*(b/d), n);
- for (int i = 0; i < d; i++)
- solutions.push_back(mod(x + i*(n/d), n));
- }
- return solutions;
- }
- // computes b such that ab = 1 (mod n), returns -1 on failure
- int mod_inverse(int a, int n) {
- int x, y;
- int d = extended_euclid(a, n, x, y);
- if (d > 1) return -1;
- return mod(x,n);
- }
- // Chinese remainder theorem (special case): find z such that
- // z % x = a, z % y = b. Here, z is unique modulo M = lcm(x,y).
- // Return (z,M). On failure, M = -1.
- PII chinese_remainder_theorem(int x, int a, int y, int b) {
- int s, t;
- int d = extended_euclid(x, y, s, t);
- if (a%d != b%d) return make_pair(0, -1);
- return make_pair(mod(s*b*x+t*a*y,x*y)/d, x*y/d);
- }
- // Chinese remainder theorem: find z such that
- // z % x[i] = a[i] for all i. Note that the solution is
- // unique modulo M = lcm_i (x[i]). Return (z,M). On
- // failure, M = -1. Note that we do not require the a[i]'s
- // to be relatively prime.
- PII chinese_remainder_theorem(const VI &x, const VI &a) {
- PII ret = make_pair(a[0], x[0]);
- for (int i = 1; i < x.size(); i++) {
- ret = chinese_remainder_theorem(ret.second, ret.first, x[i], a[i]);
- if (ret.second == -1) break;
- }
- return ret;
- }
- // computes x and y such that ax + by = c; on failure, x = y =-1
- void linear_diophantine(int a, int b, int c, int &x, int &y) {
- int d = gcd(a,b);
- if (c%d) {
- x = y = -1;
- } else {
- x = c/d * mod_inverse(a/d, b/d);
- y = (c-a*x)/b;
- }
- }
- int test() {
- // expected: 2
- cout << gcd(14, 30) << endl;
- // expected: 2 -2 1
- int x, y;
- int d = extended_euclid(14, 30, x, y);
- cout << d << " " << x << " " << y << endl;
- // expected: 95 45
- VI sols = modular_linear_equation_solver(14, 30, 100);
- for (int i = 0; i < (int) sols.size(); i++) cout << sols[i] << " ";
- cout << endl;
- // expected: 8
- cout << mod_inverse(8, 9) << endl;
- // expected: 23 56
- // 11 12
- int xs[] = {3, 5, 7, 4, 6};
- int as[] = {2, 3, 2, 3, 5};
- PII ret = chinese_remainder_theorem(VI (xs, xs+3), VI(as, as+3));
- cout << ret.first << " " << ret.second << endl;
- ret = chinese_remainder_theorem (VI(xs+3, xs+5), VI(as+3, as+5));
- cout << ret.first << " " << ret.second << endl;
- // expected: 5 -15
- linear_diophantine(7, 2, 5, x, y);
- cout << x << " " << y << endl;
- }
|