扩展中国剩余定理(主讲取模)

1.前言

扩展中国剩余定理好绕啊,很多地方取模都有讲究,所以写篇笔记来方便自己复习。


2.问题

给出一个二元组序列 \(\{(b_i,m_i)\}\),要求找出一个 \(Q\),满足要求:

\[\forall (b_i,m_i),Q \equiv b_i \pmod {m_i} \]


3.思路

  1. 找到一个都满足的解,将余数修改为这个解(记录下一个解)
  2. 将两个同余方程的模数修改为 \(lcm (m_i,m_j)\)(合并, \(lcm (m_i,m_j\) 即为新方程的周期)
  3. 继续向下合并

具体式子:
合并两个同余方程
\(Q \equiv b_i (mod m_i)\)
\(Q \equiv b_j (mod m_j)\)
合并为:
求出 \(x, y\),满足要求\(x * m_i + b_i = y * m_j + b_j\)
\(Q \equiv b_i + x * m_i \pmod {lcm (m_i, m_j)}\)


4.实现

思路相当简单,但是为了防止溢出,我们需要及时的取模,而实现的取模特别有讲究。


1.求解 \(x,y\) 的过程

由于我们合并的最终式子只有 \(x\),所以我们可以不考虑 \(y\) 的值

条件为 \(x * m_i + b_i = y * m_j + b_j\),等价于 \(x * m_i \equiv b_j - b_i \pmod {m_j}\)

所以 \(b_j - b_i\) 可以对 \(m_j\) 取模

令 \(p = delta = \frac {lcm (m_i,m_j)}{m_i}\)

则 \(x\) 可以对 \(p\) 取模

2.合并的过程

令 \(M = lcm (m_i, m_j)\),而 \(Q \equiv b_i + x * m_i \pmod {M}\)

则 \(Q(b_i + x* m_i)\) 可以对 \(M\) 取模


5.参考代码

#include <cstdio>
#include <iostream>
using namespace std;
#define LL long long
#define ULL unsigned long long

template <typename T> void read (T &x) { x = 0; T f = 1;char tem = getchar ();while (tem < '0' || tem > '9') {if (tem == '-') f = -1;tem = getchar ();}while (tem >= '0' && tem <= '9') {x = (x << 1) + (x << 3) + tem - '0';tem = getchar ();}x *= f; return; }
template <typename T> void write (T x) { if (x < 0) {x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0'); }
template <typename T> void print (T x, char ch) { write (x); putchar (ch); }
template <typename T> T Max (T x, T y) { return x > y ? x : y; }
template <typename T> T Min (T x, T y) { return x < y ? x : y; }
template <typename T> T Abs (T x) { return x > 0 ? x : -x; }

LL gcd (LL x, LL y) {
	if (y == 0) return x;
	else return gcd (y, x % y);
}
LL lcm (LL x, LL y) {
	return x / gcd (x, y) * y;
}
void exgcd (LL a, LL b, LL &x, LL &y) {
	if (b == 0) {
		x = 1; y = 0;
		return ;
	}
	exgcd (b, a % b, y, x);
	y -= (a / b) * x; 
}
LL mul (LL x, LL y, LL Mod) {
	LL res = 0;
	while (y) {
		if (y & 1) res = (res + x) % Mod;
		x = (x + x) % Mod; y >>= 1;
	}
	return res;
}
LL solve (LL a, LL b, LL c) {
	LL _gcd = gcd (a, b);
	c = (c % b + b) % b;
	if (c % _gcd != 0) return -1;
	
	LL x, y;
	exgcd (a, b, x, y);
	LL p = b / _gcd;
	x = (x % p + p) % p;
	x = mul (x, c / _gcd, p);
	return x;
}

const int Maxn = 1e5;

int n;
struct Eq {
	LL Mod, b;
}a[Maxn + 5];

int main () {
	read (n);
	for (int i = 1; i <= n; i++) {
		read (a[i].Mod); read (a[i].b);
		a[i].b %= a[i].Mod;
	}
	
	LL Mod = a[1].Mod, b = a[1].b;
	for (int i = 2; i <= n; i++) {
		LL res = solve (Mod, a[i].Mod, a[i].b - b);
		if (res == -1) {
			printf ("No Answer!");
			return 0;
		}
		LL M = lcm (Mod, a[i].Mod);
		b = (b + mul (res, Mod, M)) % M;
		Mod = M; 
	}
	printf ("%lld", b);
	return 0;
}
上一篇:在mybatis中,在列表分页查询过程中造成集合属性数据丢失的问题


下一篇:#费马小定理,BSGS#BZOJ 3285 离散对数解指数方程