数论 · 中国剩余定理（CRT）

2021 - 12 - 10：补充扩展中国剩余定理

EXCRT，额外开了一篇博客写。

2021 - 12 - 21：修改了一两句话，更严谨一些。

小奥里的韩信点兵问题：

{ x ≡ a 1 ( m o d m 1 ) x ≡ a 2 ( m o d m 2 ) ⋯ x ≡ a k ( m o d m k ) begin{cases}xequiv{a_1}pmod{m_1}\xequiv{a_2}pmod{m_2}\cdots\xequiv{a_k}pmod{m_k}end{cases} ⎩⎪⎪⎪⎨⎪⎪⎪⎧​x≡a1​(modm1​)x≡a2​(modm2​)⋯x≡ak​(modmk​)​

m m m 数组的数两两互质，求 x x x 的最小非负整数解。

构造一个数组 ans，使得 ∀   i ∈ [ 1 , k ] forall i in [1,k] ∀ i∈[1,k]：

{ a n s i ≡ 0 ( m o d m 1 ) ⋯ a n s i ≡ a i ( m o d m i ) ⋯ a n s i ≡ 0 ( m o d m k ) begin{cases}{ans_i} equiv 0 pmod{m_1}\ cdots\ {ans_i} equiv {a_i} pmod{m_i}\ cdots \ {ans_i} equiv 0pmod {m_k}end{cases} ⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧​ansi​≡0(modm1​)⋯ansi​≡ai​(modmi​)⋯ansi​≡0(modmk​)​

易得：
a n s i = ( ∏ i = 1 k m i ( i ≠ j ) ) × a i × e i ans_i = (prod_{i=1} ^ k m_i (ine j)) times a_i times e_i ansi​=(i=1∏k​mi​(i​=j))×ai​×ei​

e i e_i ei​ 为我们仍不知道的数。

不妨令 $Mgets prod_{i=1} ^ k m_i $，

就可以推出：
$
dfrac{M}{m_i} times e_i equiv 1 pmod {m_i}
$，即 e i e_i ei​ 即为 M m i dfrac{M}{m_i} mi​M​ 在取模 m i m_i mi​ 意义下的逆元。

此处用扩展欧几里得求逆元，在输入时也一起统计好 M M M。

最后的答案就是：
$
sumlimits_{i=1}^k ans_i bmod M
$

#include
using namespace std;

#define int long long
#define rint register int
int n, p;
int x, y;

inline int read ()
{
	int x = 1, s = 0;
	char ch = getchar ();
	while (ch < '0' or ch > '9') {if (ch == '-') x = -1; ch = getchar ();}
	while (ch >= '0' and ch <= '9') s = s * 10 + ch - '0', ch = getchar ();
	return x * s;
}

inline void write (int x)
{
	if (x > 9) write (x / 10);
	putchar (x % 10 ^ 48);
}

inline void exgcd (int a, int b)
{
	if (!b)
	{
		x = 1, y = 0;
		return;
	}
	exgcd (b, a % b);
	int t = x;
	x = y, y = t - a / b * y;
}

const int maxn = 15;
int a[maxn], b[maxn], ans;
int mul = 1, mi[maxn];

signed main ()
{
	n = read ();
	for (rint i (1); i <= n; ++i)
	{
		a[i] = read (), b[i] = read ();
		mul *= a[i];
	}
	for (rint i (1); i <= n; ++i)
	{
		mi[i] = mul / a[i];
		exgcd (mi[i], a[i]);
		ans += b[i] * mi[i] * (x > 0 ? x : x + a[i]);
	}
	write (ans % mul);
	return 0;
}

UVA756 Biorhythms

详见：《数论 · 扩展中国剩余定理（EXCRT）》

—— E n d End End——