最大公约数、同余原理
最大公约数
定义
两个正整数 $a$ 和 $b$ 的最大公约数（GCD，Greatest Common Divisor）是指能够同时被 $a$ 和 $b$ 整除的最大的正整数。
求解
1. 辗转相除法
辗转相除法（Euclidean algorithm）是一种求最大公约数的算法。 时间复杂度为 $O((log a)^3)$。
设 $a$ 和 $b$ 为正整数，且 $a ≥ b$， 则：
\[a = qb + r\]其中 $q$ 和 $r$ 为整数，且 $0 \leq r < b$。
则有：
\[gcd(a, b) = gcd(b, r)\]当 $r = 0$ 时，$gcd(a, b) = b$。
代码实现：
1
2
3
4
5
6
int gcd(int a, int b){ // 最大公约数
return b == 0 ? a : gcd(b, a % b);
}
int lcm(int a, int b){ // 最小公倍数
return a * b / gcd(a, b);
}
题目：第n个神奇数字
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const int mod = 1e9 + 7;
typedef long long ll;
ll __lcm(ll a, ll b) { return a * b / __gcd(a, b); } // 系统函数直接得到__gcd()
ll f(ll x, ll a, ll b) {
return x / a + x / b - x / __lcm(a, b); // 容斥原理
}
int nthMagicalNumber(int n, int a, int b) {
if (a > b) {
swap(a, b);
}
ll maxnum = (ll)n * a;
ll l = 0, r = maxnum;
while (l + 1 != r) { // 二分答案
ll m = (l + r) / 2;
if (f(m, a, b) >= n) {
r = m;
} else {
l = m;
}
}
return r % mod;
}
同余原理
- 加法、乘法每一步计算完后直接取模，减法则为 $(a-b+m)\%m$
- 要确保过程中不溢出，所以往往乘法运算的用
long long类型做中间变量 - 除法的同余需要求逆元，该博文中不做讨论，较难的题目才会涉及。
定义
对于整数 $a$ 和 $m$，$a$ 关于 $m$ 的余数（remainder）是指 $a$ 除以 $m$ 的余数，即 $a$ 除以 $m$ 得到的商的整数部分。
求解
1. 余数的定义
设 $a$ 和 $m$ 为正整数，则：
\[a = qm + r\]其中 $q$ 和 $r$ 为整数，且 $0 \leq r < m$。
则有：
\[a \equiv r \pmod{m}\]2. 同余定理
同余定理（Congruence Equation）是指对于任意的 $a$、$b$ 和 $m$，都有：
\[a \equiv b \pmod{m}\]当且仅当 $a$ 和 $b$ 关于 $m$ 同余。
3. 加法、乘法的同余
$a+b \equiv (a\%m + b\%m) \pmod{m}$
$a*b \equiv (a\%m * b\%m) \pmod{m}$
4. 减法的同余
$a-b \equiv (a\%m - b\%m) \pmod{m}$ 为了保证答案为非负数，往往会在中间变量加上 $m$，即得到 $a-b \equiv (a - b + m) \pmod{m}$。
