数论基本概念
1. 整除法
n = a k + r ( 0 ≤ r < a ) → k = ⌊ n a ⌋ n = ak + r(0 \le r < a) \to k = \lfloor \frac{n}{a} \rfloor n=ak+r(0≤r<a)→k=⌊an⌋
2. 算数基本定理
p i p_i pi 为素数，且 p i < p i + 1 p_i < p_{i + 1} pi<pi+1，则有：
n = p 1 a 1 p 2 a 2 ⋯ p m a m n = p_1^{a_1} p_2^{a_2} \cdots p_m ^ {a_m} n=p1a1p2a2⋯pmam
3. 最大公约数与最小公倍数
gcd ( a , b ) × l c m ( a , b ) = gcd ( a , b ) × a × b gcd ( a , b ) = a × b \gcd (a,b) \times lcm (a,b) = \gcd (a,b) \times \frac{a \times b}{\gcd(a,b)} = a \times b gcd(a,b)×lcm(a,b)=gcd(a,b)×gcd(a,b)a×b=a×b
4. 求一个数的约数个数
一个数的每个因子均由若干个素因子构成，第 i i i 个素因子共有 i + 1 i + 1 i+1 种取法，所以总个数为（ k k k 为素因子的总个数）：
∏ i = 1 k ( a i + 1 ) \prod_{i = 1}^{k} (a_i + 1) i=1∏k(ai+1)
代码如下：
int divisor (int n)//算数基本定理
{
int tot = 1;
for (int i = 2;i * i <= n;++i)
{
if (n % i == 0)
{
int cnt = 0;
while (n % i == 0) n /= i,++cnt;//素因子i 在 num 中的个数
tot *= (cnt + 1);
}
}
if (n > 1) tot *= 2;//剩下的 n 也为素数的情况
return tot;
}
int divisor_direct (int n)//直接暴力枚举
{
int cnt = 0;
for (int i = 1;i * i <= n;++i)
{
if (n % i == 0)
{
++cnt;
if (n / i != i) ++cnt;//完全平方数时会重复计算
}
}
return cnt;
}
素数筛法
1. 朴素筛法
将每一个数的所有倍数都筛去，时间复杂度为： O ( n 2 + n 3 + ⋯ + 1 ) O(\frac{n}{2} + \frac{n}{3} + \cdots + 1) O(2n+3n+⋯+1)。所以当 lim ( n → ∞ ) \lim(n \to \infty) lim(n→∞) 时，近似为 O ( n log n ) O(n\log n) O(nlogn)。
2. 常数优化
枚举小的那个因子。
for (int i = 2;i * i <= n;++i)
if (!flag[i])
for (int j = i * i;j <= n;j += i) flag[j] = 1;
3. 线性筛
时间复杂度为 O ( n ) O(n) O(n)。
void work (int n)//保证每个数最多被筛一次
{
for (int i = 2;i <= n;++i)
{
if (!flag[i]) p[++cnt] = i;//素数
for (int j = 1;j <= cnt;++j)
{
if (i * p[j] > n) break;//边界
flag[i * p[j]] = 1;//p[j] 是 i * p[j] 的最小素因子
if (i % p[j] == 0) break;//之后 p[j] 不为 i * p[j] 的最小素因子
//若 p[j] = 2,i = 4，则之后 p[j] = 3,i = 4 不符合条件。否则 12 = 2*6 = 3 * 4 被筛的次数 > 1
}
}
}
欧几里得算法
1. 辗转相减
若 a > b a > b a>b，则 gcd ( a , b ) = gcd ( a − b , b ) \gcd (a,b) = \gcd (a - b,b) gcd(a,b)=gcd(a−b,b)。
2. 辗转相除
若 a > b a > b a>b，则 gcd ( a , b ) = gcd ( b , a % b ) \gcd (a,b) = \gcd (b,a \% b) gcd(a,b)=gcd(b,a%b)。
int gcd (int a,int b)
{
if (a < b) swap (a,b);
return (!b) ? a : gcd (b,a % b);
}
扩展欧几里得算法
由欧几里得算法可知 a x + b y = gcd ( a , b ) ax + by = \gcd (a,b) ax+by=gcd(a,b) 一定存在一组解。那么求解 a x + b y = c ax + by = c ax+by=c 时，过程如下：
a x + b y = c ( a > b ) 设 a x ′ + b y ′ = gcd ( a , b ) 则辗转相减知 ( a − b ) × x 1 + b × y 1 = gcd ( a , b ) ∴ a × x 1 + b × ( y 1 − x 1 ) = gcd ( a , b ) ∴ x = x 1 , y = y 1 − x 1 由辗转相除代替辗转相减，则有 b × x 1 + a % b × y 1 = gcd ( a , b ) ∵ a % b = a − ⌊ a b ⌋ × b ∴ b × x 1 + ( a − ⌊ a b ⌋ × b ) × y 1 = gcd ( a , b ) ∴ a × y 1 + b × ( x 1 − ⌊ a b ⌋ × y 1 ) = gcd ( a , b ) ∴ x = y 1 , y = x 1 − ⌊ a b ⌋ × y 1 ax + by = c(a > b)\\ \texttt{设 } ax' + by' = \gcd (a,b)\\ \texttt{则辗转相减知 } (a - b) \times x_1 + b \times y_1 = \gcd (a,b)\\ \therefore a \times x_1 + b \times (y_1 - x_1) = \gcd (a,b)\\ \therefore x = x_1,y = y_1 - x_1\\ \\ \texttt{由辗转相除代替辗转相减，则有 } b \times x_1 + a \% b \times y_1 = \gcd (a,b)\\ \because a \% b = a - \lfloor \frac{a}{b} \rfloor \times b\\ \therefore b \times x_1 + (a - \lfloor \frac{a}{b} \rfloor \times b) \times y_1 = \gcd (a,b)\\ \therefore a \times y_1 + b \times (x_1 - \lfloor \frac{a}{b} \rfloor \times y_1) = \gcd (a,b)\\ \therefore x = y_1,y = x_1 - \lfloor \frac{a}{b} \rfloor \times y_1 ax+by=c(a>b)设 ax′+by′=gcd(a,b)则辗转相减知 (a−b)×x1+b×y1=gcd(a,b)∴a×x1+b×(y1−x1)=gcd(a,b)∴x=x1,y=y1−x1由辗转相除代替辗转相减，则有 b×x1+a%b×y1=gcd(a,b)∵a%b=a−⌊ba⌋×b∴b×x1+(a−⌊ba⌋×b)×y1=gcd(a,b)∴a×y1+b×(x1−⌊ba⌋×y1)=gcd(a,b)∴x=y1,y=x1−⌊ba⌋×y1
不断递归得到 gcd ( a , b ) × x + 0 × y = gcd ( a , b ) \gcd (a,b) \times x + 0 \times y = \gcd (a,b) gcd(a,b)×x+0×y=gcd(a,b)，得到特解 x = 1 , y = 0 x = 1,y = 0 x=1,y=0。
int exgcd (int a,int b,int &x,int &y)
{
int g = a;
if (b)
{
g = exgcd (b,a % b,x,y);
x -= (a / b) * y;
swap (x,y);
}
else x = 1,y = 0;//一组特解
return g;
}
设 k 1 = a ÷ gcd ( a , b ) , k 2 = b ÷ gcd ( a , b ) k_1 = a \div \gcd (a,b),k_2 = b \div \gcd (a,b) k1=a÷gcd(a,b),k2=b÷gcd(a,b)，显然 gcd ( k 1 , k 2 ) = 1 \gcd (k_1,k_2) = 1 gcd(k1,k2)=1。设 x , y x,y x,y 的最小变化单位是 d 1 , d 2 d_1,d_2 d1,d2，则此时 k 1 = d 2 , k 2 = d 1 k_1 = d_2,k_2 = d_1 k1=d2,k2=d1，所以通解是：
{ x = x + k × b gcd ( a , b ) y = y − k × a gcd ( a , b ) k ∈ Z \begin{cases} x = x + k \times \dfrac{b}{\gcd(a,b)}\\ y = y - k \times \dfrac{a}{\gcd(a,b)}\\ k \in \Z \\ \end{cases} ⎩ ⎨ ⎧x=x+k×gcd(a,b)by=y−k×gcd(a,b)ak∈Z
欧拉函数
1. 定义
ϕ ( n ) \phi(n) ϕ(n) 表示小于等于 n n n 的正整数与 n n n 互质的个数。 并且规定 ϕ ( 1 ) = 1 \phi(1) = 1 ϕ(1)=1。
2. 积性函数
设 p p p 为质数，求 ϕ ( p k ) \phi(p^k) ϕ(pk)，也就是总数减去所有 p p p 的倍数。
ϕ ( p k ) = p k − ( p k ÷ p ) = p k − p k − 1 = ( p − 1 ) × p k − 1 \phi(p^k) = p^k - (p^k \div p) = p^k - p^{k - 1} = (p - 1) \times p^{k - 1} ϕ(pk)=pk−(pk÷p)=pk−pk−1=(p−1)×pk−1
同理，求 ϕ ( p 1 k 1 × p 2 k 2 ) \phi(p_1 ^ {k_1} \times p_2 ^ {k_2}) ϕ(p1k1×p2k2)，也就是总数减去 p 1 , p 2 p_1,p_2 p1,p2 的倍数，然后再加上 p 1 × p 2 p_1 \times p_2 p1×p2 的倍数。
∴ ϕ ( p 1 k 1 p 2 k 2 ) = p 1 k 1 p 2 k 2 − p 1 k 1 − 1 p 2 k 2 × p 1 k 1 p 2 k 2 − 1 + p 1 k 1 − 1 p 2 k 2 − 1 ∴ ϕ ( p 1 k 1 p 2 k 2 ) = ϕ ( p 1 k 1 ) × ϕ ( p 2 k 2 ) \therefore \phi ({p_1} ^ {k_1} {p_2} ^ {k_2}) = {p_1} ^ {k_1} {p_2} ^ {k_2} - {p_1} ^ {
{k_1} - 1} {p_2} ^ {k_2} \times {p_1} ^ {k_1} {p_2} ^ {
{k_2} - 1} + {p_1} ^ {
{k_1} - 1}{p_2} ^ {
{k_2} - 1}\\ \therefore \phi ({p_1} ^ {k_1} {p_2} ^ {k_2}) = \phi({p_1} ^ {k_1}) \times \phi({p_2} ^ {k_2}) ∴ϕ(p1k1p2k2)=p1k1p2k2−p1k1−1p2k2×p1k1p2k2−1+p1k1−1p2k2−1∴ϕ(p1k1p2k2)=ϕ(p1k1)×ϕ(p2k2)
3. 计算通式
将 n n n 进行质因数分解，则有：
n = p 1 a 1 p 2 a 2 ⋯ p m a m ∴ ϕ ( n ) = ∏ i = 1 m p i k i − 1