这部分内容介绍了同余方程,类Euclid算法等内容

线性同余方程

对于线性同于方程axc(modb)ax \equiv c (\bmod b)

定理1,方程ax+by=cax+by = c 等价于方程axc(modb)ax \equiv c(\bmod b)
有整数解的充要条件是gcd(a,b)c\textbf{gcd}(a, b) \mid c

algorithm\textbf{algorithm}
扩展Euclid算法求解出一组x0,y0x_0, y_0,满足ax0+by0=gcd(a,b)ax_0 + by_0 = \textbf{gcd}(a, b)
两边同时除以gcd(a,b)\textbf{gcd}(a, b),再×c\times c
acx0/gcd(a,b)+bcy0/gcd(a,b)=cacx_0 / \text{gcd}(a, b) + bcy_0/ \text{gcd}(a, b) = c

cx0gcd(a,b),cy0gcd(a,b)\frac{cx_0}{\text{gcd}(a, b)}, \quad \frac{cy_0}{\text{gcd}(a, b)}

定理2, 若gcd(a,b)=1\text{gcd}(a, b) = 1,并且x0,y0x_0, y_0 是方程
ax+by=cax + by = c 的一组解,那么方程的任意解可以表示为
tZ,x=x0+bt,y=y0at\forall t \in \mathbb{Z}, \quad x = x_0 + bt, y = y_0 - at

因为此时tt 为任意整数都可以成立,这个时候我们可以求出方程的所有解
但实际问题中,我们只需要求解一个最小整数解就可以了

实际上,根据定理1,我们可以把一般解式表示为

x=cx0gcd(a,b)+kbgcd(a,b)y=cy0gcd(a,b)kagcd(a,b)kZ\begin{gathered} x = \frac{cx_0}{\text{gcd}(a, b)} + k \cdot \frac{b}{\text{gcd}(a, b)} \\ y = \frac{cy_0}{\text{gcd}(a, b)} - k \cdot \frac{a}{\text{gcd}(a, b)} \\ \forall k \in \mathbb{Z} \end{gathered}

注意到kk 可以取任意整数
方程的通解实际上是

modbgcd(a,b)xcx0gcd(a,b)\bmod \frac{b}{\text{gcd}(a, b)} \equiv x \equiv \frac{cx_0}{\text{gcd}(a, b)}

就是一类同余数,modbgcd(a,b)\bmod \frac{b}{\text{gcd}(a, b)}余数是

cx0gcd(a,b)\frac{cx_0}{\text{gcd}(a, b)}

最小的数,一般取k=1k = 1,此时对一个特解xx

t=bgcd(a,b),x=(xmodt+t)modtt = \frac{b}{\text{gcd}(a, b)}, \quad x = (x \bmod t + t) \bmod t

LOJ2605 同余方程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
ll a, b;

ll exgcd(ll a, ll b, ll &x, ll &y) {
if (b == 0) {
x = 1, y = 0;
return a;
}

ll d = exgcd(b, a%b, x, y);
ll z = x; x = y; y = z - (a/b)*y;
return d;
}

int main() {
freopen("input.txt", "r", stdin);
cin >> a >> b;

ll x, y;
exgcd(a, b, x, y);
ll res = (x % b + b) % b;
cout << res << endl;
}

扩展Euclid算法求解线性同余方程

axc(modb)ax \equiv c(\bmod b)
也就是ax+by=cax + by = c 方程的解,要求求出一个最小的xx

  • algorithm\textbf{algorithm}
    • d=exgcd(a,b,x,y)get xd=\textbf{exgcd}(a, b, x, y) \Rightarrow \text{get }x
      计算出一个特解xx
    • cmodd0c \bmod d \neq 0,没有解
      else k=c/d\textbf{else} \ k = c/d
      x(xk)modb,y(yk)modbx \leftarrow (x \cdot k) \bmod b, \quad y \leftarrow (y \cdot k) \bmod b
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
inline ll exgcd(ll a, ll b, ll &x, ll &y) {
if (!b) {
x = 1, y = 0;
return a;
}
ll d = exgcd(b, a%b, x, y);
ll z = x; x = y; y = z - (a/b) * y;
return d;
}

bool liEu(ll a, ll b, ll c, ll &x, ll &y) {
ll d = exgcd(a, b, x, y);
if (c % d) return 0;

int k = c/d;
x = (x * k) % b;
y = (y * k) % b;
return 1;
}

中国剩余定理

CRT01
CRT02

mim_i 不再两两互质情况下的中国剩余定理

POJ2891
POJ2891
假设解完前kk 个线性同余方程之后得到的特解是xx
m=lcm(m1,m2,,mk)m = \textbf{lcm}(m_1, m_2, \cdots , m_k)
通解可以表示成x+km(kZ)x + km (k \in \mathbb{Z})
最小非负整数解为xmodmx \bmod m

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
typedef unsigned long long ull;
int n;

inline ll exgcd(ll a, ll b, ll &x, ll &y) {
if (!b) {
x = 1, y = 0;
return a;
}
ll d = exgcd(b, a%b, x, y);
ll z = x; x = y; y = z - (a/b) * y;
return d;
}

void solve(int n) {
ll a, r;
cin >> a >> r;
ll ans = r, lcm = a;
bool fl = true;

n--;
while (n--) {
cin >> a >> r;

// exgcd
r = (r - ans % a + a) % a;
ll x, y, x2;
ll d = exgcd(lcm, a, x, y);
if (r % d) fl = false;
else x2 = x * (r/d) % a;

ans += x2 * lcm;
// update lcm, and get min ans
lcm = (lcm / d) * a;
ans = (ans % lcm + lcm) % lcm;
}

if (fl) cout << ans << endl;
else cout << "-1" << endl;
}

void init() {
//
}

int main() {
freopen("input.txt", "r", stdin);
while (cin >> n) {
init();

solve(n);
}
}

CRT算法图解

CRTalgo

高次同余方程