数论
Zzzzzzzm
·
·
个人记录
数论
逆元
### 线性求逆元
假设现在要求的$i$的逆元
考虑带余除法，设$p=iq+r$，则有$iq+r\equiv 0(\mod p)
注意到p是质数，因此r不为0，r的逆元存在。
等式两边同时乘i^{-1}r^{-1}，得到qr^{-1}\equiv0(\mod p)
因此i^{-1}\equiv-qr^{-1}\equiv-(p/i)(p\mod i)^{-1}(\mod p)。
费马小定理
若p是质数，则a^{p-1}\equiv1(\mod p),a\in Z。
费马小定理实质上是欧拉函数的一种特例。
欧拉函数
$1$~$N$中与$N$互质的数的个数被称为欧拉函数，记为$\varphi(N)$。
若在算数基本定理中，$N=p_1^{c_1}p2^{c_2}\ldots p_m^{c^m}$。
$$
\varphi(N)=N\times \frac{p_1-1}{p_1}\times \frac{p_2-2}{p_2}\times\ldots\times \frac{p_m-1}{p_m}=N\times\prod_{质数p|N}{(1-\frac{1}{p})}
$$
```c++
int phi(int n){
int ans = n;
for(register int i = 2; i * i <= n; ++i)
if(n%i == 0){
ans = ans / i * (i-1);
while(n%i == 0) n /= i;
}
if(n > 1) ans = ans / n * (n-1);
return ans;
}
```
### 线性欧拉函数
```c++
for(register int i = 2; i <= n; ++i){
if(!vis[i]){ //i是质数
prime[primen++] = i;
phi[i] = i-1; //质数的欧拉函数是比它少一
}
for(register int j = 0; j < primen; ++j){
if(i*prime[j] > n) break;
vis[i*prime[j]] = 1;
if(i % prime[j] != 0) //积性函数
phi[i*prime[j]] = phi[i]*phi[prime[j]];
else{ //若x是质数p的倍数，则phi[x]=phi[x/p]*p
phi[i*prime[j]] = phi[i]*prime[j];
break; //保证只筛一次
}
}
}
```
## 最大公约数
### 如何计算$gcd
负数的gcd即用两者的绝对值求解，含0的即为0。
\gcd(a,b)=\gcd(a-b,b)=\gcd(b,a-b)=\gcd(b,a\mod b)
时间复杂度
约为log n。
证明设k = n \mod a， a < n则总有k \leq \frac{n}{2}。
当$a > \frac{n}{2}$，则$k = n-a < \frac{n}{2}$，
得证。
## 筛法
### $Eratoshenes$筛法
时间复杂度$O(n\log^2(n))
线性筛法
时间复杂度O(n)
for(register int i = 2; i <= n; ++i){
if(not_prime[i]) prime[++prime_cnt] = i;
for(register int j = 1; j <= prime_cnt; ++j){
if(prime[j]*i > n) break;
not_prime[prime[j]*i] = true;
if(i%pimre[j] == 0) break;
}
}
裴蜀定理
裴蜀定理，一个关于最大公约数的定理
内容
对于\forall a,b\in Z,且a，b不同时为0,总\exist x,y \in Z,ax+by = gcd(a, b).
证明1
-
对于任意一个数等于0,则gcd(a， b) = 0, 此时显然成立。
-
若a， b不等于0.
$\therefore$不妨设$0 < b \leq a，\gcd(a，b) = b
对ax + by = d，两边同时除以d，a_1 \times x + b_1 \times y = 1，其中\gcd(a_1, b_1) = 1。
转证a_1 \times x + b_1 \times y = 1。
\gcd(a,b) \rightarrow \gcd(b, a \mod b) \rightarrow \ldots
我们把取模后的数据叫做r。于是，有
\gcd(a1,b1) = \gcd(b1,r1)=\gcd(r1,r2)=\ldots=\gcd(r_{n-1},r_n)=1
把辗转相除法运算展开，做成带余数除法，得
\begin{cases}
a_1=q_1b+r_1 & 0 \leq r_1 < b1\\
b_1=q_2r_1+r_2 & 0 \leq r_2 < r1\\
r_1=q_3r_2+r_3 & 0 \leq r_3 < r_2\\
\dots\\
r_{n-3}=q_{n-1}r_{n-2}+r_{n-1} \\
r_{n-2}=q_nr_{n-1}+r_n \\
r_{n-1}=q_{n+1}r_n \\
\end{cases}
最后一项r_n=1，
r_{n-2} = x_nr_{n-1}+1
即
1=r_{n-1}-x_nr_{n-1}
由倒数第三个式子r_{n-1}=r_{n-3}-x_{n-1}r_{n-2}代入上式，得
1=(1+x_nx_{n-1})r_{n-2}-x_nr_{n-3}
然后逐一向上代入消去r_{n-2}, \dots, r_1.
可证得1=a_1x+b_1y.
证明2
假设bx+(a\mod b)y = \gcd(b, a\mod b)，我们记为x_1, y_1，即bx_1+\left(a-\frac{a}{b}\times b\right)y_1=\gcd(b,a\mod b)。即bx_1+\left(a-\frac{a}{b}\times b\right)y_1=\gcd(a, b)，则有ay_1+b\left(x_1-\frac{a}{b}\times y_1\right)=\gcd(a,b)，这时我们令x_2=y_1,y_2=x_1-\frac{a}{b}\times y_1，则我们找到了ax+by=\gcd(a,b)的一组解，利用归纳法证毕。
例题 CF510D Fox And Jumping
题目解析
由裴蜀定理可得，当$\gcd(x,y)=1$时，总存在$a,b\in Z$，满足$ax+by=1$。
然后我们发现这就像是一个最短路一样，每一个路有花费，起点为$0$，终点为$1$。
于是
```c++
#include<bits/stdc++.h>
using namespace std;
unordered_map<int,int> vis;
unordered_map<int, long long> dis;
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> q;
int c[305], n, l[305];
template<typename T>
inline void read(T&x){
x = 0; char q; bool f = 1;
while(!isdigit(q=getchar())) if(q == '-') f = 0;
while(isdigit(q)){
x = (x<<1) + (x<<3) + (q^48);
q = getchar();
}
x = f?x:-x;
}
template<typename T>
inline void write(T x){
if(x < 0){
x = -x;
putchar('-');
}
if(x > 9) write(x/10);
putchar(x%10+'0');
}
inline int gcd(int x, int y){
if(x%y == 0) return y;
gcd(y, x%y);
}
int main(){
read(n);
for(register int i = 1; i <= n; ++i) read(l[i]);
for(register int i = 1; i <= n; ++i) read(c[i]);
dis[0] = 0;
q.push(make_pair(0, 0));
while(!q.empty()){
int u = q.top().second;
q.pop();
if(u == 1) break;
if(vis.find(u) != vis.end()) continue;
vis[u] = 1;
for(register int i = 1; i <= n; ++i){
int v = gcd(u, l[i]);
if(dis.find(v) == dis.end()) dis[v] = 1e18;
if(dis[v] > dis[u]+c[i]){
dis[v] = dis[u]+c[i];
q.push(make_pair(dis[v], v));
}
}
}
if(dis.find(1) == dis.end()) write(-1);
else write(dis[1]);
return 0;
}
```
## $exgcd
同时也可以用逆元来求解，$ax+by=1$的一组解$x$，就有$ax=1(\mod m)
中国剩余定理
假设m_1,m_2,\ldots,m_n两两互素，则对于任意的整数a_1,a_2,\ldots,a_n方程组
\begin{cases}
x \equiv a_1(\mod m_1)\\
x \equiv a_2(\mod m_2)\\
\ldots\\
x \equiv a_n(\mod m_n)
\end{cases}
都存在整数解，且若X,Y都满足该方程组的解，则必定有X \equiv Y (\mod N)，其中N = \prod_{i=1}^{n}{m_i}
具体而言，x \equiv \sum_{i=1}^{n}{a_i}\times\frac{N}{m_i}\times[(\frac{N}{m_i})^{-1}]_{m_i}(\mod N)。
excrt
假设已经求出前k-1个方程组成的同余方程的一个解为x。
则有M=\prod^{k-1}_{i-1}{m_i}。
则前k-1个方程组的通解为x+i\times M(i\in Z)。
那么对于加入第k个方程组后的方程组
我们要求一个正整数t，使得x+t\times M\equiv a_k(\mod m_k)
转化一下上述式子得t\times M \equiv a_k-x(\mod m_k)
对于这个式子我们已经可以通过扩展欧几里得求解t
若该同余式无解，则整个方程组无解，若有，则前k个同余方程式组成的方程组的一个解解为x_k=x+t\times M
所以整个算法的思路就是求解k次扩展欧几里得。
威尔逊定理