7/22 数论 P1
概念
a, b 的最大公因数，记 $\gcd(a, b)$，$a, b$ 的最小公倍数，记 $\text{lcm}(a, b)$。
\gcd
辗转相除法：求 a 和 b 的最大公因数，等于求 b 和 a \mod b 的最大公因数。
int gcd(int a, int b) {
if (!b) return a;
return gcd(b, a % b);
}
C++11 以上可以使用 __gcd() 求最大公因数。
如果 a 和 b 互质，$\gcd(a, b) = 1$。对于任何一个正整数 $p$，$p$ 和 p - 1 一定互质。
\text{lcm}
$\text{lcm}(a, b) = \frac{ab}{\gcd(a, b)}$。
分解质因数
for (int i = 2; i <= sqrt(n); i++) {
if isPrime(i) {
while (!x % i) {
x /= i;
cnt[i]++;
}
}
}
预处理质数筛法优化：把所有合数筛掉，留下来的一定都是质数。
考虑到任意合数的倍数一定被其质因子枚举过，因此只需要将每个质数的任意倍筛除即可。复杂度 $O(n \log \log n)$。
for (int i = 2; i <= n; i++) {
if (isPrime(i)) {
for (int j = 2 * i......n) isPrime[j] = 0;
}
}
还能优化，考虑让每个数只被其最小质因子筛除。
for (int i = 2; i <= n; i++) {
if (!vis[i]) p[++cnt] = i;
for (int j = 1; i * p[j] <= n; j++) {
vis[i * p[j]] = 1;
if (i % p[j] == 0) break;
} // j 是质数表下标
}
复杂度 $O(n)$。
取模
如果 a \mod b = c ，则 $ma \mod b = mc \mod b$。
取模在加、减、乘法中都可以分配，但除法不行。
如果 $a \mod c = b \mod c$，则 $c | (a - b)$。
同余
如果 a 和 b 在模 c 的意义下余数相同，则称 a 和 b 在模 c 的意义下同余，写作 $a \equiv b (\mod c)$。
如果 $a \equiv b (\mod c)$，且 k 为 a, b, c 的公因数，则 $\frac{a}{k} \equiv \frac{b}{k} (\mod \frac{c}{k})$。
如果 $a \equiv b (\mod c)$，且 $k | c$，则 $a \equiv b (\mod k)$。
逆元
$\text{inv}(i) = (b - \frac{b}{i}) \times \text{inv}(b \mod i)$。
int n, p;
cin >> n >> p;
inv[1] = 1;
cout << 1 << endl;
for (int i = 2; i <= n; i++) {
inv[i] = (p - p / i) * inv[p % i] % p;
}
费马小定理
若 p 为质数，且 a 不为 p 的倍数，则 $a^{p - 1} \equiv 1 (\mod p)$。
-
若 ac \equiv bc (\mod m) 且 $\gcd(c, m) = 1$，则 $a \equiv b (\mod m)$。
-
若 $\gcd(a, m) = 1$，则 a, 2a, 3a, \dots, (m - 1)a 是一个模 m 的完全剩余系（对 m 取模，余数取遍 $1, 2, 3, \dots, m - 1$）。
由上述定理可知，${1, 2, 3, \dots, p - 1} 和 {a, 2a, 3a, \dots, (p - 1)a}$ 是模 p 的完全剩余系，$(p - 1)! = (p - 1)! \times a^{p - 1} (\mod p)$。
对于模数是质数的情况，有 $a^{p - 1} = 1$，即 $a \times a^{p - 2} = 1$。
快读
读入速度：裸 cin < scanf < cin 关同步 < 快读。
inline int read() {
int res = 0, ch = getchar();
while (!isDigit(ch)) ch = getchar();
while (isDigit(ch)) {
res = res * 10 + (ch - '0');
res %= MOD; // 直接对 MOD 取余
ch = getchar();
}
return res;
}
例题
P1069 [NOIP2009 普及组] 细胞分裂
求满足 {S_i} ^ k | {m_1}^{m2} 的最小 $k$。