- 分享
Rosmarinus の 奇妙数论学习笔记
- 2021-10-3 23:14:47 @
介绍
简单概括一下情况的话就是 CSP 和 NOIP 近在眼前但是 Rosmarinus 有关数论的部分几乎全部不会……所以 Ros 痛并思痛下定决心苦学数论。
也是因为前段时间在 Luogu 里发帖求资料下面只有一堆铜球所以干脆自己写一个。
这里的内容会随着 Ros 的学习进度不断更新,虽说主要是给自己看的但是我也会尽量让大家都能看懂(请相信我的教学水平),所以这是一个造福社会的东西。
前面的内容可能会比较简单。
目录
- 同余
- 逆元
- 质数
- 约数
- 欧拉函数
- 欧拉定理
- 快速幂
- 裴蜀定理
- 扩展欧几里得算法
- 中国剩余定理
- 组合数
- 卢卡斯定理
感谢名单
感谢来自 @Sya_Resory、@dengziyue、@GuidingStar、@lzxxzl 等大佬的指正。
同余
定义
对于类似于 的式子为同余方程,读作「 与 在模 意义下同余」。
含义
表示 ,在 C++
中可以表示为 a % m == b % m
。
性质
-
反身性:;
-
对称性:若 ,则 ;
-
传递性:若 ,,则 ;
-
相加:若 ,,则 ;
-
相乘:若 ,,则 ;
-
相除:若 ,则 ;
特殊的,若 ,则 。
相对地,若 ,,则 。
-
幂运算:若 ,则 ;
-
若 (),则 ,其中 表示 的最小公倍数。
逆元
定义
若对于正整数 满足 ,则称 为 的逆元,记作 (注意,在这里 不是 的负一次方, 是一个整数)
性质
对原式进行移项即可
求法
- 当 是质数:
具体证明请见「费马定理」。
- 否则
扩展欧几里得定理。
说说我对逆元的理解
如你们所见, 在我们之前的学习中代表着 的倒数,也就是
那为什么在这里又不一样了呢?
其实你可以尝试类比一下:
- 在 中, 可以表示为 ;(我不知道可不可以这么说)
但是呢?在同余系(我不知道是不是叫这个名字的)的定义域为 ,也就是说是不能出现小数的。
但是啊,在同余系中,我们虽然不可以使用 ,但是我们可以使用 。
所以,共同点:
- 在 中,;
- 在同余系中,。
所以啊,逆元其实就是同余系中的除法。
提一嘴,我们的编程老师:「纯粹的除法可是一个很稀有的东西!」
所以说,当我们今后遇到一个带有除法的需要取模的式子,只要将除 转化为乘 的逆元即可正常操作。
质数
定义
质数和合数是针对所有大于 的「自然数」来定义的(所有小于等于 的数都不是质数)。
所有小于等于 的整数既不是质数也不是合数。
质数的判定——试除法:
代表的含义是 能被 整除。(这里的 |
代表整除,在 C++
中可以表示为 n % d == 0
)
一个合数的约数总是成对出现的,如果 ,那么 ,因此我们判断一个数是否为质数的时候,只需要判断较小的那一个数能否整除 就行了,即只需枚举 ,即 , 就行了。
sqrt(n)
这个函数执行的时候比较慢。
代码:
bool is_prime(int x)
{
if(x < 2) return false;
for(int i = 2; i <= x / i; i ++) // x / i 是最快且最不容易爆炸的写法
{
if(x % i == 0) return false;
}
return true;
}
分解质因数——试除法(算数基本定理)
算数基本定理:任何一个大于 的自然数 ,如果 不为质数,那么 可以唯一分解成有限个质数的乘积 ,这里 均为质数,其中指数 是正整数。
特别要注意——分解质因数与质因数不一样,分解质因数是一个过程,而质因数是一个数。
一个合数分解而成的质因数最多只包含一个大于 的质因数。(反证法,若 可以被分解成两个大于 的质因数,则这两个质因数相乘的结果大于 ,与事实矛盾)
当枚举到某一个数 的时候, 的因子里面已经不包含 里面的数(已经被除干净了),如果 ,则 的因子里面也已经不包含 里面的数,因此每次枚举的数都是质数。
质因子(质因数)在数论里是指能整除给定正整数的质数。根据算术基本定理,不考虑排列顺序的情况下,每个正整数都能够以唯一的方式表示成它的质因数的乘积。
两个没有共同质因子的正整数称为互质。因为 没有质因子, 与任何正整数(包括 本身)都是互质。
只有一个质因子的正整数为质数。
代码:
void divide(int x)
{
for(int i = 2; i <= x / i; i ++)
{
if(x % i == 0)
{
int s = 0;
while(x % i == 0) x /= i, s ++ ;
cout << i << ' ' << s << endl;
}
}
if (x > 1) cout << x << ' ' << 1 << endl; // 大于sqrt(n)的数
cout << endl;
}
筛质数(朴素筛法)
步骤:把 中的所有的数的倍数都标记上,最后没有被标记的数就是质数。
原理:假定有一个数 未被 中的数标记过,那么说明,不存在 中的任何一个数的倍数是 ,也就是说 中不存在 的约数,因此,根据质数的定义可知: 是质数。
调和级数:当 趋近于正无穷的时候,$\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\dots+\frac{1}{n}=\ln n+c$( 是欧拉常数,约等于 左右)
时间复杂度:约为 (注:此处的 特指以 为底)
埃氏筛(稍加优化版的筛法)
质数定理: 中有 个质数。
步骤:在朴素筛法的过程中只用质数项去筛。
时间复杂度:。
代码:
int primes[N], cnt; // primes[] 存储所有素数
bool st[N]; // st[x] 存储 x 是否被筛掉
void get_primes(int n)
{
for(int i = 2; i <= n; i ++)
{
if(st[i]) continue;
primes[cnt ++] = i;
for(int j = i + i; j <= n; j += i) st[j] = true;
}
}
线性筛
若 ,线性筛和埃氏筛的时间效率差不多,若 ,线性筛会比埃氏筛快了大概一倍。
核心: 内的合数 只会被其最小质因子筛掉。(算数基本定理)
原理: 之内的任何一个合数一定会被筛掉,而且筛的时候只用最小质因子来筛,然后每一个数都只有一个最小质因子,因此每个数都只会被筛一次,因此线性筛法是线性的。
枚举到 的最小质因子的时候就会停下来,即 if(i % primes[j] == 0) break;
当 i % primes[j] != 0
时,primes[j]
一定小于 的最小质因子,primes[j]
一定是 primes[j]*i
的最小质因子。
当 i % primes[j] == 0
时,primes[j]
一定是 的最小质因子,而 primes[j]
又是 primes[j]
的最小质因子,因此 primes[j]
是 primes[j]*i
的最小质因子。
代码
int primes[N], cnt; // primes[]存储所有素数
bool st[N]; // st[x]存储x是否被筛掉
void get_primes(int n)
{
for(int i = 2; i <= n; i ++)
{
if(!st[i]) primes[cnt ++] = i;
// j < cnt 不必要,因为 primes[cnt - 1] = 当前最大质数
// 如果 i 不是质数,肯定会在中间就 break 掉
// 如果 i 是质数,那么 primes[cnt - 1] = i,也保证了 j < cnt
for(int j = 0; primes[j] <= n / i; j ++)
{
st[primes[j] * i] = true;
if(i % primes[j] == 0) break;
}
}
}
约数
试除法求所有约数
代码
int divisors[N], cnt; // divisors[] 存储所有约数
void get_divisors(int x)
{
for(int i = 1; i <= x / i; i ++)
{
if(x % i == 0)
{
divisors[++ cnt] = i; // 约数总是成对出现
if(i * i != n) divisors[++ cnt] = n / i; // 需要判断是否重复
}
}
}
求一个数所有的约数个数
公式
若 ,则 的约数个数为 。
-
证明
对于任意一个 的约数 ,, 均成立,因此 的个数就是 的所有可能的取法的个数,且 的不同取法对应的 均不相同。
小知识
在 int
范围内,约数个数最多的数的约数个数约为 个。
代码
const int MOD = 1e9 + 7;
void get_divisors_num(int x) // 求 x 的约数个数
{
unordered_map<int, int>primes;
for(int i = 2; i <= x / i; i ++)
{
while(x % i == 0)
{
primes[i] ++;
x /= i;
}
}
if(x > 1) primes[x] ++;
long long ans = 1;
for(auto prime : primes) ans = ans * (prime.second + 1) % MOD; // 一个神奇的能够遍历 map 中所有元素的写法
cout << ans << endl;
}
求一个数所有约数的和
公式
若 ,则 的所有约数的和为
$$(P_1^{0}+P_1^1+P_1^2+\dots+P_1^{a_1})(P_2^{0}+P_2^1+P_2^2+\dots+P_2^{a_2})\dots(P_k^{0}+P_k^1+P_k^2+\dots+P_k^{a_k}) $$代码
const int MOD = 1e9 + 7;
void get_divisors_sum(int x) // 求 x 的所有约数的和
{
unordered_map<int, int>primes;
for(int i = 2; i <= x / i; i ++)
{
while(x % i == 0)
{
primes[i] ++;
x /= i;
}
}
if(x > 1) primes[x] ++;
long long ans = 1;
for(auto prime : primes)
{
int p = prime.first, a = prime.second;
long long t = 1;
for(int i = 1; i <= a; i ++) t = (t * p + 1) % MOD; // 为什么可以这么写,自己证吧
ans = ans * t % MOD;
}
cout << ans << endl;
}
欧几里得算法(辗转相除法)
小性质 1
若 ,,则 ,。不证。
小性质 2
。
-
证明:
;
设 ,则有 ;
设 的任意一个公约数为 ,即 ,;
,,;
;
;
的任意一公约数,都是 的公约数,即左右两者等价;
;
即:;
证毕。
代码
int gcd(int a, int b) // 求 a, b 的最大公约数
{
return b ? gcd(b, a % b) : a;
}
欧拉函数
定义
表示 中与 互质的数的个数。
如 ,分别为 。
特别的,。
公式
设 ,则 $\varphi(n)=n(1-\frac{1}{P_i})(1-\frac{1}{P_2})(1-\frac{1}{P_3})\dots(1-\frac{1}{P_k})$。
证明
已知:
-
为积性函数,即若 ,;
不会证,记结论吧。
-
对于任意一质数 ,;
由质数的定义可得。
-
对于任意一质数 ,$\varphi(p^a)=p^a-\frac{p^a}{p}=p^a-p^{a-1}=p^a(1-\frac{1}{p})$ ;
由于 是质数,所以 只有 一个质因数,则在 的范围内,只有 这 个数与 不互质。因此,根据定义得,。
因此,对于 :
$$\varphi(n)=\varphi(p_1^{a_1})\varphi(p_2^{a_2})\dots\varphi(p_k^{a_k})=P_1^{a_1}(1-\frac{1}{P_1})P_2^{a_2}(1-\frac{1}{P_2})\dots P_k^{a_k}(1-\frac{1}{P_k})=n(1-\frac{1}{P_i})(1-\frac{1}{P_2})\dots(1-\frac{1}{P_k}) $$证毕。
代码
void get_phi(int x) // 求 phi(x)
{
if(x == 1)
{
cout << "1\n";
return;
}
int res = x;
for(int i = 2; i <= x / i; i ++)
{
if(x % i == 0)
{
res = res / i * (i - 1);
while(x % i == 0) x /= i;
}
}
if(x > 1) res = res / x * (x - 1);
cout << res << endl;
}
线性筛
欧拉函数线性筛能够在 的时间内求出 。
代码仅仅是在线性筛筛质数的情况下增加了几句话。
先上代码:
int primes[N], cnt; // primes[]存储所有素数
int phi[N];
bool st[N]; // st[x]存储x是否被筛掉
void get_phi(int n)
{
phi[1] = 1; // 特殊规定
for(int i = 2; i <= n; i ++)
{
if(!st[i])
{
primes[cnt ++] = i;
phi[i] = i - 1; // 质数的性质
}
for(int j = 0; primes[j] <= n / i; j ++)
{
st[primes[j] * i] = true;
if(i % primes[j] == 0)
{
phi[i * primes[j]] = phi[i] * primes[j]; // 注释 1
break;
}
phi[i * primes[j]] = phi[i] * (primes[j] - 1); // 注释 2
}
}
}
-
注释 :
令
primes[j]
的值为 ,显然 为质数。则在
i % primes[j] == 0
时,即 ,此时, 与 的质因数完全相同。由于 仅与 的质因数本身,与 的质因数次数无关,因此 (用言语完全无法表述清楚,请读者自行思考)。
-
注释 :
令
primes[j]
的值为 ,显然 为质数。则在此时,,即 互质。
根据积性函数定义,$\varphi(i\times p)=\varphi(i)\times \varphi(p)=\varphi(i)\times(p-1)$。
欧拉定理
内容
若 ,即 与 互质,则 。
证明
设在 中,所有与 互质的数分别为 。
则在 中,不存在 与 ,。
-
证明:
若存在 ,则 ;(同余性质)
由于 ,故 ;
则 ;
则 ;
与现实矛盾。
故不存在 ,即 在模 意义下互不相同。
因此, 与 在模 意义下为顺序不同的同一组数;
因此,$a^{\varphi(n)}\times x_1x_2\dots x_{\varphi(n)}\equiv x_1x_2\dots x_{\varphi(n)}\pmod{n}$;
因此,。
快速幂
虽然这个应该不算数论但是应该也问题不大吧?
前置知识
(初中数学)
思路
对于 ( 是一个很大的数),将 转化为二进制,即 ,我们只需要算出 即可。
时间复杂度:。
代码
const long long N = 1e9 + 7;
void quick_mi(long long a, long long b) // 求 a ^ b % MOd
{
long long t = a, ans = 1;
while(b)
{
if(b % 2 == 1) ans = ans * t % MOD; // b & 1 即为 b % 2 == 1,但是速度会快一点
t = t * t % MOD;
b /= 2;
}
cout << ans % MOD << endl;
}
例题:快速幂求逆元
题目描述
给定 ,其中 是质数,求 在模 意义下的乘法逆元。
前置知识
费马定理:若 ,则 。
具体做法
由于 为质数,因此:
- 若 ,则一定不存在逆元;
- 否则,。
因此,,即 。
因此, 即为我们要求的逆元。
代码
略。
裴蜀定理
对于任意一对正整数 ,一定存在非零整数 满足 ,同时 是满足条件的 的最小正整数和。
-
证明
设 , 则 ;
- 证明:由于 ,,因此 ,即 。
因此, 一定是最小正整数和。
关于存在性证明请见扩展欧几里得算法。
扩展欧几里得算法
本体
直接上代码:
int exgcd(int a, int b, int &x, int &y) // 求出 ax + by = gcd(a, b) 的一组可行解
{
if(!b)
{
x = 1, y = 0; // 当 b = 0 时,显然 x = 1, y = 0 就是一组可行解
return a;
}
int d = exgcd(b, a % b, y, x); // 注释 1
y -= a / b * x;
return d;
}
注释 1
因为 翻转了所以我们把 也翻转一下;
在此次递归结束后,应当有:;
即为: ;
又为:;
因此,令 ,就又回到了原来的式子:。
一直递归即可求出最终解。
此时返回的 只是一组解,若要求通解,则令 ,则 的通解为 ,则 的最小正整数解即为 。
关于裴蜀定理
由以上代码得,一定能返回一组可行解。
因此,裴蜀定理成立。
而对于 ,有解的充要条件为 。
例题:线性同余方程
题目描述
给定正整数 ,求出一个 满足 。
思路分析
对式子做一些变形:
,使得 ;
即为:;
设 ,则 ;
有解的充要条件为:
代码
略。
中国剩余定理
内容
给定 个两两互质的整数 ,我们需要解决如下线性同余方程组:
$\begin{cases}x\equiv a_1\pmod{m_1}\\x\equiv a_2\pmod{m_2}\\\dots\\x\equiv a_k\pmod{m_k}\end{cases}$
令 ,, 表示 在模 意义下的逆元。
则有:$x=a_1M_1M_1^{-1}+a_2M_2M_2^{-1}+\dots + a_kM_kM_K^{-1}$。
一般题目会要求输出最小的正整数解,此时输出 即可。
证明
暂时不会。
先挖个坑。
组合数
定义
表示在 个数中取 个数的方案数。
公式
证明
可以换个角度证明,若我们在做一道题目,用 表示从 个苹果中取 个的方案数,稍微思考一下就可以推出:。都在学数论了这个应该能明白。
例题
题目描述
给定 ()组询问,每组询问给定两个正整数 (),求 。
思路分析
考虑到数据范围,预处理出所有 不太现实,因此我们考虑另外一种做法:
若要求:,即
设 ,
则 $C_a^b\bmod p=fact(a)\times infact(b)\times infact(a-b)$
与 数组可以在线性时间内预处理。
时间复杂度:
代码
#define LL long long
const int MOD = 1e9 + 7;
const int N = 1e5 + 10;
int fact[N], infact[N];
int qmi(int a, int k, int p) // qmi = quick_mi,快速幂
{
int ans = 1;
while(k)
{
if(k & 1) ans = (LL)ans * a % p;
a = (LL)a * a % p;
k >>= 1;
}
return ans;
}
void pre() // 预处理
{
fact[0] = infact[0] = 1; // 边界
for(int i = 1; i <= N; i ++) fact[i] = (LL)fact[i - 1] * i % MOD;
for(int i = 1; i <= N; i ++) infact[i] = (LL)infact[i - 1] * qmi(i, MOD - 2, MOD) % MOD; // 费马定理
}
void Work()
{
int a, b;
scanf("%d %d", &a, &b);
printf("%d\n", (LL)fact[a] * infact[a - b] % MOD * infact[b] % MOD);
}
int main()
{
int T;
pre();
scanf("%d", &T);
while(T --) Work();
return 0;
}
卢卡斯定理
内容
对于非负整数 和质数 都有:$C_a^b\equiv C_{a\bmod p}^{b\bmod p}\times C_{\lfloor a\div p\rfloor}^{\lfloor b\div p\rfloor}\pmod{p}$
证明非常麻烦,建议直接记结论,若有需要请自行百度。
或者等我闲下来之后回来更新。
例题
题目描述
给定三个正整数 (,),其中 是质数,求
思路分析
显然不能直接算。
考虑到 不大,因此可以直接上卢卡斯定理。
时间复杂度:
代码
#define LL long long
int qmi(int a, int k, int p)
{
int ans = 1;
while(k)
{
if(k & 1) ans = (LL)ans * a % p;
a = (LL)a * a % p;
k >>= 1;
}
return ans;
}
int C(int a, int b, int p) // 求组合数
{
if(b > a) return 0; // 边界条件
int ans = 1;
for(int i = 1, j = a; i <= b; i ++, j --) // 因为 a,b 不会超过 p 因此直接对着原始公式爆算即可
{
ans = (LL)ans * j % p;
ans = (LL)ans * qmi(i, p - 2, p) % p; // 为什么要乘逆元你们懂得吧?
}
return ans;
}
int lucas(LL a, LL b, int p)
{
if(a < p && b < p) return C(a, b, p); // 边界条件
return (LL)C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}
卡特兰数
定义
对于类似于:可以将长度为 的问题分解成长度为 ()的两个子问题的问题都可以使用卡特兰数求解。
这也就是原始公式: 的由来。
公式
9 comments
-
doc LV 7 @ 2023-10-23 23:44:16
qpzc
-
2021-10-6 12:33:48@
tql
-
2021-10-6 0:31:57@
在 Ros 这里,HydroOJ = Blog
-
2021-10-5 16:34:55@
mobai!!!!!!1
-
2021-10-4 13:45:17@
orz
-
2021-10-4 12:57:23@
捉几个虫
- 是啥/yiw
- 欧拉函数一般用 吧(
$\varphi$
)
-
2021-10-4 12:30:16@
%%%
-
2021-10-4 10:26:38@
orz
-
2021-10-4 0:20:30@
建议
折叠
- 1