数学专题

线性筛素数

int pj[N], cnt, vis[N];

void get_primes(int n) {
	for(int i = 2; i <= n; i ++) {
		if(!vis[i])	   pj[++ cnt] = i;
		for(int j = 1; pj[j] * i <= n; j ++) {
			vis[pj[j] * i] = true;
			if( i % pj[j] == 0)    break; 
		} 
	}
}

唯一分解定理：(x = prod p_{i} ^ {a_{i}})

约数个数定理： (prod (a_i + 1))

约数个数和定理: (prodsum_{i = 0}^{a_i}p_j^i)

最大公约数: (gcd(a,b) = gcd(b, a mod b))

线性筛phi

(φ(n) = N prod (1 - frac{1}{p_i}))

void get_primes(int n) {
    phi[1] = 1;
    for(int i = 2; i <= n; i ++) {
	if(!vis[i])	   primes[++ cnt] = i, phi[i] = i - 1;
	for(int j = 1; primes[j] * i <= n; j ++) {
	    vis[primes[j] * i] = true;
	    if( i % primes[j] == 0) {
	    phi[i * primes[j]] = phi[i] * primes[j];
	    break; 
	}
	phi[i * primes[j]] = phi[i] * (primes[j] - 1);
    }
}

欧拉定理：

[a ^{φ(n)} equiv 1 quad(mod n) ]

其中，((a,n)=1)

证明：
引入一个概念：缩系

[R_n = {c_1, c_2, c_3, .... .c_{φ(n)} }, quad (c_i, n) = 1 ]

同时乘上a，也是mod n 的一个缩系，因为乘上a之后，两两互不同余,并且仍然与n互质。

[prod_{i = 1}^{φ(n)}c_i equiv prod_{i = 1}^{φ(n)}ac_i ]

即

[prod_{i = 1}^{φ(n)}c_i equiv a^φ(n) prod_{i = 1}^{φ(n)}c_i ]

两边约去公因数，得到欧拉定理。

如果 (n)为素数，可以得到 费马小定理：

[a^{p - 1} equiv 1quad(mod p) ]

由此，可以得到

[a * a^{p - 2} equiv 1quad(mod p) ]

所以，如果模数是素数，那么a的逆元就是(a^{p-2}),可以用快速幂求。

扩展欧几里得exgcd：

exgcd求解方程

[ax +b y = gcd(a,b) ]

由于

[gcd(a,b) = gcd(b,a mod b) ]

所以，我们可以写成和上面的方程一样的形式：

[b x + (a mod b)y = gcd(a,b) ]

进一步化简

[bx + (a - lfloor frac{a}{b} floor b)y = gcd(a, b) ]

[ay + b(x - lfloor frac{a}{b} floor y) = gcd(a, b) ]

所以

[x' = y, y' = x - lfloor frac{a}{b} floor y ]

通解

[x_k = x_0 + frac{kb}{gcd(a, b)}, y_k = x_0 - frac{ka}{gcd(a, b)} ]

代码：

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

中国剩余定理

给定 (2n) 个整数(a_1,a_2,…,a_n)和(m_1,m_2,…,m_n,)求一个最小的非负整数 (x)，满足(∀i∈[1,n],x≡m_i(mod a_i))并且模数两两互质。
首先，设

[M = prod_{i = 1}{n} b_i ]

[m_i = frac{M}{bi} ]

求解

[m_i * m_i^{-1} equiv 1 ]

[x = sum_{i = 1}^{n}a_i * m_i * m_i^{-1} ]

for(int i = 1; i <= n; i ++) {
	scanf("%lld%lld", &mo[i], &re[i]);
	M *= mo[i];
}
for(int i = 1; i <= n; i ++) {
	m[i] = M / mo[i];
	LL tmp;
	exgcd(inv[i], tmp, m[i], mo[i]);
}
LL ans = 0;
for(int i = 1; i <= n; i ++) {
	ans += (re[i] * m[i] * inv[i]);
}
printf("%lld
", (ans % M + M) % M);

扩展中国剩余定理exCRT

首先考虑两个方程,
(x ≡ a_1(mod m_1))

(x ≡ a_2(mod m_2))

进一步，写成等式:
(x = k_1 * m_1 + a_1)
(x = k_2 *m_2 + a_2)
两式相等，得到：
(k_1 *m_1-k_2*m_2 = a_1-a_2)
只有(k_1)与(k_2)是未知数，可以用exgcd进行求解。
令(d = gcd(m_1, m_2)),那么，(k_1)的通解为(k_t = k_1 + t * frac{m_2}{gcd(m_1,m_2)})
所以(x = k_t * m_1 +a_1 = t * frac{m_1m_2}{d} +k_1*m_1+a_1)
所以，我们将两个方程合并为一个方程，我们重新令(m_1 = lcm(m_1,m_2), k_1 = k_1*m_1 +a_1)
------------恢复内容开始------------