初等数论
\(\mathcal{P}art\) 1.基础概念
- 整除
对两个正整数 \(a\),\(b\)(\(b\le a\)),如果存在一个整数 \(k\) 使得 \(a=kb\),则称 \(b\) 整除 \(a\),记作 \(b|a\)
- 带余除法
对任何整数 \(a\) 和正整数 \(b\),一定存在一个整数 \(r\in[0,b)\) 和一个整数 \(k\),使得 \(a=kb+r\),称上式为 \(a\) 和 \(b\) 的带余除法式, \(r\) 称为 \(a\) 除以 \(b\) 的余数
- 因数
对一个正整数 \(x\),所有能整除 \(x\) 的正整数均为 \(x\) 的因子
- 公因数
两个正整数 \(x,y\) 共有的因数称为它们的公因数
- 质数
因数只有 \(1\) 和自身的正整数叫做质数;\(1\) 不是质数
- 质因子
对 \(x\) 的因数中是质数的那部分被称为质因子
- 算数基本定理
对任何一个大于 \(1\) 的整数 \(x\),\(x\) 均能表示成若干个 \(x\) 的质因子的乘积。这个表示法是唯一的
\(\mathcal{P}art\) 2.基础算法
- 因数分解
\(\mathcal{O}(\sqrt{x})\) 对任意正整数 \(x\) 分解因子
- 埃氏筛:
\(\mathcal{O(\log{\log{n}})}\) 的筛出 \(n\) 以内的质数
- 质因子分解
\(\mathcal{O}(\sqrt{x})\) 对任意正整数 \(x\) 分解质因子
证明不可能会有两个大于 \(\sqrt{x}\) 的数
易证
- 欧几里得算法
\(\gcd(a,b)=\gcd(b,a\bmod b)\)
\(\mathcal{Part}\) 3.线性筛
先给出代码
void getPrime(const int N = 100000000) {
for (int i = 2; i <= N; ++i) {
if (!np.test(i)) {
prm.push_back(i);
}
for (auto j : prm)
if (i * j <= N) {
int k = i * j;
np.set(k);
if (i % j == 0) break;
} else break;
}
}
上述代码的时间复杂度为 \(\mathcal{O}(n)\)
- 正确性证明:
我们设一个合数 \(x\),使得 \(x=py,p\in \mathbb{P}\),且 \(p\) 为最小的
\(p\) 为最小的,则 \(y\) 的因子里没有比 \(p\) 小的
则一定会枚举到 \(i=y\),\(j=p\) 的情况,则 \(x\) 一定会被筛掉
- 线性证明:
想要是线性,则要证明每个合数只会被筛一遍
我们设一个合数 \(x\),使得 \(x=py=qz\) 满足 \(p,q\in\mathbb{P},\gcd(p,q)=1,p<q\)
则 \(p\) 一定是 \(z\) 的因子
所以当 \(i=z,j=p\) 时就会退出,就会导 致 \(x\) 只会被筛一遍
证毕
- 性质
因为 \(x\) 只会被它最小筛掉,所以可求一个数的最小质因子
\(\mathcal{Part}\) 4.不定方程
- 定义
形如 \(ax+by=c\),其中 \(a,b,c\) 是已知数的方程叫做二元一次不定方程
- 引理
方程 \(ax+by=c\) 有解当且仅当 \(\gcd(a,b)|c\)
证明:
记住就行
- 求解 (exgcd进行求解)
因为 \(\gcd(a,b)|c\),所以我们设 \(\cfrac{c}{\gcd(a,b)}=k,k\in \mathbb{N^*}\)
因此我们只需要求 \(ax+by=\gcd(a,b)\) 即可,最后 \(x,y\) 同乘 \(k\) 即可
\[ax+by=\gcd(a,b)=\gcd(b,a\bmod b)=bx'+(a\bmod b)y'=bx'+(a-\lfloor \cfrac{a}{b}\rfloor\times b)y' \]接下来给等式左右边做个系数对应,即
\[ax+by=ay'+b(x'-\lfloor \cfrac{a}{b} \rfloor y') \]所以递归求解后答案是
\[\begin{cases} x=y'\\ y=x'-\lfloor \cfrac{a}{b} \rfloor y' \end{cases} \]- 边界
显然,最后的边界是 \(b=0\),考虑前面的一个式子
显然 \(b|a\),方程为
\[ax''''+by''''=b \]显然有解
\[\begin{cases} x''''=0\\ y''''=1 \end{cases} \]即解决
- 代码
void Ex_gcd(const ll a, const ll b, ll &X, ll &Y) {
if (a % b == 0) {
X = 0; Y = 1;
} else {
Ex_gcd(b, a % b, Y, X);
Y ‐= a / b * X;
}
}
\(\mathcal{Part}\) 5.同余方程
- 定义
对两个整数 \(a,b\) 如果他们除以 \(d\) 的余数相同,则称它们模 \(d\) 同余,记作 \(a\equiv b\pmod d\)
- 性质
在同余号两侧同时加、减、乘任何整数,同余式仍成立
显然,\(a,b,r\) 的带余除法表达式等价为 \(a\equiv r\pmod b\)
\(\mathcal{Part}\) 6.威尔逊定理
正整数 \(p\) 是质数的充分必要条件是 \((p-1)! \equiv -1\pmod p\)
啥用没有,记住就行
\(\mathcal{Part}\) 7.欧拉函数
- 定义
定义欧拉函数 \(\varphi(n)\) 表示小于等于 \(n\) 的数中与 \(n\) 互质的数的个数。特别的,\(\varphi(1)=1\)
显然,\(\varphi(p)=p-1,p\in \mathbb{P}\)
- 性质
-
积性:如果 \(\gcd(a,b)=1\) 则 \(\varphi(a\times b)=\varphi(a)\times \varphi(b)\)
-
欧拉反演:\(\sum_{d|n}\varphi(d)=n\)
-
性质三:对任何质数 \(p\),\(\varphi(p^k)=p^k-p^{k-1}\)
证明:
\(p^k\) 个数中,有 \(p^{k-1}\) 个数跟 \(p^k\) 不互质,即 \(1p,2p…p^{k-1}p\)
即证
- 计算
- 单个欧拉函数:
设 \(n\) 的唯一分解式为 \(n=p_1^{k_1}…p_s^{k_s}\) 根据积性,\(\varphi(n)=\prod_{i=1}^s \varphi(p_i^{k_i})=\prod_{i=1}^{s}p^{k_i}-p^{k_i-1}\)
- 线性筛欧拉函数:
在线性筛的同时求出欧拉函数,设 \(k\) 的最小质因子为 \(j\),则 \(i=\cfrac{k}{j}\)
分三种情况讨论
- \(k\) 为质数时,明显的 \(\varphi(k)=k-1\)
- \(i\) 和 \(j\) 互质时,根据积性,\(\varphi(k)=\varphi(i) \times \varphi(j)\)
- \(j|i\) 时,\(\varphi(k)=j\times \varphi(i)\),推导如下:
设 \(k=j^q\times p\),其中 \(p\) 不含 \(k\) 的最小质因子,则:
\[\begin{aligned} \varphi(k)&=\varphi(j^q)\times \varphi(p)\\ &=(j^{q}-j^{q-1})\times \varphi(p)\\ &=j(j^{p-1}-j^{p-2})\times \varphi(p)\\ &=j\times\varphi(j^{p-1}) \times \varphi(p)\\ &=j\times\varphi(i) \end{aligned} \]即证
\(\mathcal{Part}\) 8. 逆元
我们不能再同余符号两边除以一个数,但是我们需要进行这样的操作怎么办?
这时候引出逆元
定义 \(x^{-1}\) 满足 \(xx^{-1}\equiv 1 \pmod{p}\),这个时候就做到了除法的感觉
- 性质
- 逆元存在性定理:当 \(x\) 在模 \(p\) 同余下有逆元当且仅当 \(\gcd(x,p)=1\),\(0\) 没有逆元
- 逆元唯一性定理:模 \(p\) 同余下,一个整数 \(x\) 的逆元若存在,则唯一,注意这里的逆元是在 \([1,p)\) 之间的
- 一个数的逆元的逆元等于它本身
- 计算
- exgcd求解
对于给定的 \(x,p\),显然 \(x\times x^{-1} \equiv 1\pmod{p}\),把它改成带余除法式即为
\(x\times x^{-1}=kp+1\),改下顺序,注意这里 \(k\) 是系数,正负号没要求,即为
\(x\times x^{-1}+pk=1\),由不定方程存在性定理可得 \(\gcd(x,p)|1\),根据逆元存在性定理可以得到这个不定方程是有解的
用exgcd求解即可
- 这里介绍欧拉定理和费马小定理
欧拉定理:对于任意正整数 \(a,m\) 且 \(\gcd(a,m)=1\),一定有:\(a^{\varphi(m)}\equiv 1\pmod{m}\),当 \(m\) 为质数时,由 \(\varphi(m)=m-1\),此定理退化为:
费马小定理:对任意正整数 \(a\) 和任意质数 \(p\),有 \(a^{p-1}\equiv 1 \pmod{p}\)
- 费马小定理求解
根据费马小定理,\(a^{p-1}\equiv 1\pmod{p}\),两侧同乘 \(a^{-1}\) 得到 \(a^{-1}\equiv a^{p-2} \pmod{p}\)
于是得到了逆元的你一种求法:快速幂求出 \(a^{p-2}\bmod p\) 即可
注意这里 \(p\) 为质数,常用的质数为:
\[\begin{aligned} 1145141\\ 19260817\\ 10^9+7\\ 10^7+7\\ 998,244,353 \end{aligned} \]一定要记住
- 线性筛逆元
令 \(inv_i\) 为 \(i\) 在模 \(p\) 意义下的逆元,则:
\[inv_i\equiv -\lfloor\cfrac{p}{i} \rfloor \times inv_{p \ \bmod \ i}\pmod{p} \]证明:
写出 \(i\) 在模 \(p\) 意义下的带余除法式为:\(p=ki+r\),两边对 \(p\) 取余,得到
\(ki+r\equiv 0\pmod{p}\)
移项:\(r\equiv-ki\pmod{p}\)
同乘 \(i^{-1}r^{-1}\),得 \(i^{-1}\equiv -kr^{-1}\pmod{p}\)
注意到:\(k=\lfloor\cfrac{p}{i} \rfloor\),\(r=p\bmod i\),即证
Inv[1] = 1;
for (int i = 2; i <= n; i ++)
Inv[i] = (p - p / i) * Inv[p % i] % p;//这里避免他是负数
- 组合数逆元
- 正推:
显然,我们要预处理出 \((x!)^{-1}\)
我们先预处理出 \(x^{-1}\),显然 \((x!)^{-1}=((x-1)!) ^{-1}\times x^{-1}\)
这种方式要预处理出 \(x^{-1}\) 效率很低,我们考虑另一种方法
- 逆推
直接用费马小定理求出 \((n!)^{-1}\),然后根据 \((i!)^{-1}=((i+1)!)^{-1} \times i\),反着地推回去即可
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN = 5e6 + 7, Mod = 998244353;
int T, N;
ll F[MAXN], Inv[MAXN];
ll qpow(ll a, ll b) {
ll ans = 1;
while (b) {
if (b & 1) ans = ans * a % Mod;
a = a * a % Mod, b >>= 1;
}
return ans;
}
int main () {
ios :: sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> T >> N;
F[0] = 1;
for (int i = 1; i <= N; i ++) F[i] = F[i - 1] * i % Mod;
Inv[N] = qpow(F[N], Mod - 2);
for (int i = N - 1; i >= 0; i --) Inv[i] = Inv[i + 1] * (i + 1) % Mod;
ll ans = 0;
while (T --) {
ll a, b;
cin >> a >> b;
ans ^= (F[a] * Inv[b] % Mod * Inv[a - b] % Mod);
}
cout << ans << '\n';
return 0;
}
\(\mathcal{Part}\) 9.中国剩余定理(CRT)
现在我们要解出一个同余方程组形如:
\[\begin{cases} x \equiv a_1 \pmod{m_1}\\ x \equiv a_2 \pmod{m_2}\\ x \equiv a_3 \pmod{m_3}\\ \cdots \ \cdots\ \cdots\ \cdots \end{cases} \]其中保证 \(m_i\) 两两互质,求 \(x\) 的通解
- \(\mathcal{Solution}\)
我们转换下题意,也就是我们要求一个 \(S\) 使得其:
\[x \equiv S \equiv a_i \pmod{m_i} \]现在我们尝试构造 \(S\)
规定 \(M=\prod m_i\),\(M_i=\cfrac{M}{m_i}\),\(t_i\) 是在模 \(m_i\) 下 \(M_i\) 的逆元
我们根据 \(x \equiv a_i \pmod{m_i}\) 和 \(t_i M_i \equiv 1\pmod{m_i}\),两边同乘1可得:
\(x\equiv a_iM_it_i \pmod{m_i}\)
现在我们令 \(j\ne i\),则有 \(M_j\equiv 0\pmod{m_i}\),两边同乘得到:\(a_jM_jt_j\equiv 0\pmod{m_i}\)
我们将原式加上0可以得到:\(x\equiv a_iM_it_i+a_jM_jt_j\pmod{m_i}\)
我们将所有 \(j\) 都加起来,可以得到 \(x\equiv \sum a_iM_it_i \pmod{m_i}\)
我们发现 \(\sum a_iM_it_i\) 是个定值,设其为 \(S\)
于是我们现在就满足 \(x\equiv S \pmod {m_i}\)
现在只需要证明 \(S\equiv a_i \pmod{m_i}\) 即可
很容易发现 \(t_iM_i\) 在模 \(m_i\) 下为 1 的,即证明了
根据简单的推导,可以得到通解为:
\(S+Mk(k\in \mathbb{N+})\)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 27;
int n;
ll A[MAXN], B[MAXN], ans, M[MAXN], m = 1;
void Ex_gcd(const ll a, const ll b, ll &X, ll &Y) {
if (a % b == 0) {
X = 0; Y = 1;
} else {
Ex_gcd(b, a % b, Y, X);
Y -= a / b * X;
}
}
int main () {
cin >> n;
for (int i = 1; i <= n; i ++) {
cin >> A[i] >> B[i];
m = m * A[i]; }
for (int i = 1; i <= n; i ++) {
M[i] = m / A[i];
ll x = 0, y = 0;
Ex_gcd(M[i], A[i], x, y); x = (x + A[i]) % A[i];
ans += B[i] * M[i] * x; ans %= m;
}
cout << ans << '\n';
return 0;
}
\(\mathcal{Part}\) 10. 尾声
数论还有很多定理等着你去了解
标签:gcd,数论,ll,varphi,times,pmod,初等,equiv From: https://www.cnblogs.com/Phrvth/p/17511037.html