基础数论¶
0、前言¶
同余、GCD、LCM、拓展GCD¶
视频链接:
https://www.bilibili.com/video/BV1XR4y1u7Bb/
素数相关¶
视频链接: https://www.bilibili.com/video/BV1Cu411U7Ls/
快速幂和矩阵快速幂和逆元¶
视频链接:
https://www.bilibili.com/video/BV1j3411e7qh/
一、同余¶
1.1 结论¶
- \((a+b)\mod\ n=((a\mod\ n)+(b \mod \ n) )\mod\ n\)
- \((a-b)\mod\ n =((a\mod\ n) - (b \mod \ n) )\mod \ n\)
- \((a \times b) \mod \ n = ((a \mod \ n) \times (b \mod \ n) )\mod \ n\)
二、GCD&LCM¶
2.1 GCD¶
GCD即最大公约数,小学的时候我们就学习了求两数的最大公约数的方法。但是要注意如果有一个数为0的话那么最小公约数就是另一个不为0的数,我们在这里只需要知道GCD是什么东西就行了
2.1.1 更相减损法¶
两个正整数a和b(a>b),它们的最大公约数等于a-b的差值c和较小数b的最大公约数。
2.1.2代码:¶
int gcd_3(int a,int b) {//更相减损法 递归写法
if(a == 0)
return b;
if(b == 0)
return a;
if(a == b)
return a;
if(a > b)
return gcd_3(a-b,b);
if(a < b)
return gcd_3(b-a,a);
}
int gcd_4(int a,int b) {//更相减损法 循环写法
if(a == 0)
return b;
if(b == 0)
return a;
while(a != b) {
if(a > b)
a -= b;
else
{
int t = a;
a = b - a;
b = t;
}
}
return a;
}
2.1.3 辗转相除法¶
两个正整数a和b(a>b),它们的最大公约数等于a除以b的余数c和b之间的最大公约数。
其实就是把更相减损变得更高级一点(加减运算变乘除运算,提升了一个级别)
但是大整数取模会让一些题极为头疼,所以我们还是要慎重考虑什么时候用更相减损什么时候用辗转相除。
2.1.4 代码¶
int gcd_1(int a,int b){//辗转相除法 循环写法
while(b > 0) {
int t = a%b;
a = b;
b = t;
}
return a;
}
int gcd_2(int a,int b) {//辗转相除法 递归写法
return b?gcd_2(b,a%b) : a;
}
2.2 LCM¶
LCM即最小公倍数,小学的时候也学过,当我们求出GCD的时候,LCM也就出来了,
2.3 拓展欧几里得¶
2.3.1 前置知识¶
辗转相除法、贝祖定理
- 辗转相除法就是不断的让较大的数模上较小的数,最后使得其中一个数位0,最后得到答案
- 贝祖定理:\(ax+by=c,x∈Z*,y∈Z*\) 成立的充要条件是 \(gcd(a,b)|c\)
贝祖定理证明:
设\(s=gcd(a,b)\),显然\(s|a\),并且\(s|b\)
又因为\(x,y∈Z\)
所以\(s|ax\),\(s|by\)
显然要使得之前的式子成立,则必须满足\(c\)是\(a\)和\(b\)的公约数的倍数
又因为\(x\)和\(y\)是正整数
所以\(c\)必然是\(a,b\)最大公约数的倍数。
因此,证得该定理成立
当然我这里写的可能只有两元,但是这个定理可以拓展到n元,请大家思考拓展到n元的情况
2.3.2 问题引出¶
求得任意一组解:\(ax+by=1\)
2.3.3 思路¶
很显然,我们能知道如果\(gcd(a,b)!=1\)的话是无解的,所以我们只看\(gcd(a,b)=1\)的情况,通过拓展欧几里得的算法我们可以解决这一类问题
2.3.4 拓展欧几里得算法代码¶
int ex_gcd(int a,int b,int &x,int &y)//返回的值还是GCD(a,b)
{
if(b==0)//等于0的情况直接返回了
{
x=1;
y=0;
return a;
}
int ans=ex_gcd(b,a%b,x,y);//获得x',y';
int temp=x;//存储x'
x=y;//x=y'
y=temp-(a/b)*x;//y=x'-(a/b)*y'
return ans;
}
2.3.5 原理证明¶
若\(ax+by=c\)有解,且设\(t = gcd(a,b)\),则\(c \% t =0\)
①设\(ax+by=t\)
当b等于0时,\(t=a\),因为\(gcd(a,0)=a\),则会有\(a\times x = a\),即\(x=1\)
② 当b不等于0时
设\(ax+by=gcd(a,b)\) ---Ⅰ
我们可以推出下一层的状态:\(bx'+(a\%b)y'=gcd(b,a\%b)\) --- Ⅱ
又因为\(gcd(b,a\%b)=gcd(a,b)\) --- Ⅲ
所以由Ⅰ、Ⅱ、Ⅲ可得:\(ax+by=bx'+(a\%b)y'\) ---Ⅴ
又因为\(a\%b = a - \left \lfloor \frac{a}{b} \right \rfloor \times b\) --- Ⅵ
所以由Ⅴ、Ⅵ可得:\(ax + by = a*y' + b\times (x'- \left \lfloor \frac{a}{b} \right \rfloor \times y')\)
所以可以得到:\(x = y',y = x'- \left \lfloor \frac{a}{b} \right \rfloor \times y'\)
三、唯一分解定理¶
3.1 理论¶
正整数的唯一分解定理,即:每个大于1的自然数均可写为 质数 的积,而且这些素因子按大小排列之后,写法仅有一种方式。
3.2习题¶
http://120.78.128.11/Challenge.jsp#B213
四、素数三大筛¶
4.1 朴素素数筛¶
4.1.1 原理¶
地球人都知道一个合数A的因子肯定是小于等于\(\sqrt{A}\)的,那么我们就能得到朴素素数筛的方法遍历查找到\(\sqrt{A}\)即可,复杂度\(O(\sqrt{N})\)
4.1.2 代码¶
bool is_prime(int x) {
if(x == 0 || x == 1)
return false;
for(int i = 2; i*i <= x; ++i) {//这里用乘法是为了避免开根号的精度误差
if(x % i == 0)//如果找到了因子,那么该数就不是质数
return false;
}
return true;
}
4.2 埃式筛¶
4.2.1 原理¶
埃式筛的原理就是通过对已知的质数进行加倍操作,我们就能得到这个质数的大于2的整数倍数都是合数(因子就是该倍数),这样通过筛选N范围以内的质数就能得到所有的质数,总体复杂度:\(O(nloglogn)\)
4.2.2 代码¶
/*
作者:Mangata
埃式筛模板
*/
//时间复杂度 :O(n*log(log(n)))
#include<cstdio>
#include<algorithm>
#include<cstring>
const int N = 10000005;
bool vis[N] = {true,true};//初始化
int main()
{
int n,x;//离线处理
for(int i = 2; i*i <= N; ++i) {
if (!vis[i]) {
for(int j = i*2; j <= N; j += i) //把素数的倍数筛掉
vis[j] = true;
}
}
while(~scanf("%d",&x)) {
if (vis[x])
puts("No");
else
puts("Yes");
}
return 0;
}
4.3 欧拉筛¶
4.3.1 原理¶
欧拉筛的思想和埃式筛一样,都是通过对质数的倍数进行筛选,但是有一点不同的是我们在对质数的倍数都进行标记的时候,这里我们其实是重复操作了的,而欧拉筛就能避免重复筛选,让每个合数只被它的最小质因子筛选一次,以达到\(0(N)\)的时间复杂度。
核心操作体现在:if (i % prime[j] == 0) break;
前置知识:任何合数都能表示成多个素数的积。所以,任何的合数肯定有一个最小质因子。我们通过这个最小质因子就可以判断什么时候不用继续筛下去了
简单证明:
-
当\(i\%prime[j] == 0\)时,那么就有\(k \times prime[j] = i;\)
-
设\(i\times prime[j + 1] = X\)(一个未知任意合数)
-
则:\(i \times prime[j+1] = prime[j] \times k \times prime[j+1] = X\)
-
又∵ \(prime[j + 1] > prime[j]\)
-
∴\(prime[j + 1] \times k \ >\ prime[j] \times k\)
-
∴ \(prime[j+1] \times (k \times prime[j]) = x = i \times prime[j+1]\)
- 所以可得,\(i \times prime[j+1]\)必然会在以后被\(prime[j]\)的\(k \times prime[j + 1]\)倍数删掉
- 后面的数字同理
4.3.2 代码¶
/*
作者:Mangata
欧拉筛模板
*/
//时间复杂度为 O(n)
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
const int N = 10000005;
int prime[N];
bool vis[N];
void get_prime() {
memset(vis,true,sizeof vis);
memset(prime,0,sizeof prime);
vis[0] = vis[1] = false;
for(int i = 2; i <= N; ++i) {
if (vis[i]) {
prime[++prime[0]] = i;
}
for(int j = 1;j <= prime[0] && i * prime[j] <= N; ++j) {
vis[i * prime[j]] = false;
if (i % prime[j] == 0) //避免重复筛选
break;
}
}
}
int main()
{
int n;
get_prime();
while(~scanf("%d",&n)) {
if (vis[n])
puts("Yes");
else
puts("No");
}
return 0;
}
4.4 拓展:米勒罗宾¶
对比较大的质数进行一个检测(有一定随机性)
五、矩阵运算¶
5.1 矩阵加减法¶
直接对应位置相加减即可
5.2 矩阵乘法¶
矩阵乘法就是\(A\)矩阵的第\(i\) 行 和\(B\)矩阵的第\(j\) 列 进行乘法运算,并作为结果矩阵C的\(C[i][j]\) 元素
5.3 代码¶
#include<bits/stdc++.h>
using namespace std;
#define N 100
struct Matrix{
int n,m;
int mp[N][N];
void init(int n,int m) {
this->n = n;
this->m = m;
}
};
Matrix add(Matrix L,Matrix R) {//加法
if(L.n != R.n || L.m != R.m) return L;
Matrix M;
for(int i = 0;i < L.n; ++i) {
for(int j = 0;j < L.m; ++j){
M.mp[i][j] = L.mp[i][j] + R.mp[i][j];
}
}
return M;
}
Matrix reduce(Matrix L,Matrix R) {//减法
if(L.n != R.n || L.m != R.m) return L;
Matrix M;
for(int i = 0;i < L.n; ++i) {
for(int j = 0;j < L.m; ++j){
M.mp[i][j] = L.mp[i][j] - R.mp[i][j];
}
}
return M;
}
Matrix mult(Matrix L,Matrix R) {//乘法
if(L.n != R.m || L.m != R.n) return L;
Matrix M;
for(int i = 0;i < L.n; ++i) {
for(int j = 0;j < R.m; ++j){
for(int k = 0;k < L.m; ++k) {
M.mp[i][j] += L.mp[i][k] * R.mp[k][j];
}
}
}
return M;
}
int main()
{
Matrix a,b;
a.init(2,2);
b.init(2,2);
for(int i = 0;i < 2; ++i) {
for(int j = 0;j < 2; ++j) {
a.mp[i][j] = i * 2 + j;
b.mp[i][j] = i * 2 + j;
}
}
Matrix c = mult(a,b);
for(int i = 0;i < 2; ++i) {
for(int j = 0;j < 2; ++j) {
printf("%d ",c.mp[i][j]);
}
putchar('\n');
}
return 0;
}
六、快速幂&龟速乘¶
6.1快速幂¶
6.1.1 问题引出¶
给出三个数a、b、c,求\(a^b \ mod \ c\)
运用前面学到的同余,我们可以直接对a进行乘b次然后取模c,但是当b很大的时候怎么办呢?这时候就要用到了今天的内容,快速幂,快速幂作为一个基础的知识,在很多的地方都会用到它,例如求高幂运算,求逆元、矩阵快速幂等
6.1.2 原理¶
快速幂的原理其实用到了位运算的知识,我们的关注点应该是这个幂b,之前的方法是直接循环乘b次,但是当b很大例如1e9的时候就不满足时间复杂度,我们可以将这个b先转化为二进制,我举个栗子:
例如b = 11,那么它的二进制就为1011B
,也就是说我们要求的这个\(a^b \ = \ a^1 \times a^2 \times a ^ 8\) 不难看出我们将这个b分解成了若干个2的幂的积,我们通过位运算只需要通过不断的左移维护一个2的幂的值即可,当该位为1那么就乘上它,这就是快速幂的原理,时间复杂度为\(log_b\)
6.1.3 代码¶
//快速幂
ll ksm(ll x, ll n, ll mod) {
ll res = 1;
while(n > 0) {
if(n & 1)
res = (res * x)% mod;
x = (x * x) % mod;
n >>= 1;
}
return res;
}
6.2广义幂¶
6.2.1问题引出¶
已知数列 \(a_1,a_2……a_n\)和\(C\)
计算 \((a_1 \times a_2 \times ……\times a_n) \%C\)的结果
6.2.2原理¶
设:○为一种运算且与集合V构成群,a∈V,e为○运算的幺元。
即e满足对于任意的a,有 \(e○a\ = \ a○e\ =\ a\)
我们可以记
\(a^○=e\)
\(a_n\ =\ a_{n-1}\ ○\ a\)
则有以下性质
\(a_n\ +\ m\ =\ a_n\ ○\ a_m\)
则此时计算a关于○运算的n次幂的快速幂可以这样写
res=e;temp=a;
while(n)
{
if(n&1)
res=res○temp;
temp=temp○temp;
n>>=1;
}
return res;
然后就像\(a^b=a\times a\times a\times a\times a…\) 是关于乘法的幂运算,又因为\(1\times a\ =\ a \times 1 \ =\ a\),所以乘法幺元e就是1,带入上面的程序就可以得到最常见的乘法快速幂,下面的龟速乘同理
6.3 龟速乘法¶
6.3.1问题引出¶
如果我们想要计算两个大整数A、B(long long范围内)的乘法并取模C怎么办呢?手动写高精度吗?显然不需要,这里就能用到我们现在要学的龟速乘法
6.3.2原理¶
和上面的快速乘同理,不难看出此处的此处的乘法幺元就是0,如果还是不懂请看上面的广义幂的原理
6.3.3 代码¶
ll gsc(ll x, ll n, ll mod) {
ll res = 0;
x%= mod;
n%= mod;
while(n) {
if(n & 1)
res = (res + x) % mod;
x = (x%mod + x%mod) % mod;
n >>= 1;
}
return res%mod;
}
七、矩阵快速幂¶
7.1问题引出¶
求一个\(N\times N\)矩阵的K次幂
我们之前学过矩阵的加减乘,知道乘法的复杂度为\(O(N^3)\)的,如果朴素的做法就是\(O(N^3 \times k)\)的,当k很小的时候我们这样计算倒没问题,但是当k很大的时候呢,这时候就需要到这一小节的内容,矩阵快速幂
7.2原理¶
原理参见上面的广义幂,实质和快速幂,龟速乘等没有太大区别只不过幺元不同,此处的幺元变成了单位矩阵(主对角线全为1,其余为0),运算方式变成了矩阵乘法
7.3 代码¶
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define N 200
struct Matrix{
ll mp[N][N];
};
Matrix loc;
ll n,k;
Matrix operator*(const Matrix &x, const Matrix &y) {
Matrix a;
memset(&a,0,sizeof(a));
for(int i = 1;i <= n; ++i)
for(int j = 1;j <= n; ++j)
for(int k = 1;k <= n; ++k)
a.mp[i][j] = ((a.mp[i][j] + x.mp[i][k] * y.mp[k][j]) % mod) %mod;
return a;
}
void ksm(ll k) {
Matrix ans;
for(int i = 1;i <= n; ++i)
for(int j = 1;j <= n; ++j)
ans.mp[i][j] = i==j;
while(k) {
if(k & 1) ans = ans * loc;
loc = loc * loc;
k>>=1;
}
for(int i = 1;i <= n; ++i) {
for(int j = 1;j <= n; ++j) {
printf("%lld ",ans.mp[i][j]);
}
putchar('\n');
}
}
int main()
{
scanf("%lld%lld",&n,&k);
for(int i = 1;i <= n; ++i)
for(int j = 1;j <= n; ++j)
scanf("%lld",&loc.mp[i][j]);
ksm(k);
return 0;
}
7.5矩阵快速幂求解斐波那契问题¶
7.5.1 问题引出¶
众所周知斐波那契问题\(F_n = F_{n-1} + F_{n-2}\),我们可以通过递推式求出取模情况下的第N项的值,但是如果N很大呢(比如1e18),这时候怎么办呢?
7.5.2 思路¶
很显然我们能想到用一个矩阵乘法来表达这个递推过程
然后我们此时假设P=\(\begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}\) 就能得到斐波那契的矩阵递推式:
我们就能在\(log_n\)的时间复杂度求出\(F_n\)了
7.5.3 斐波那契数列性质¶
- 卡西尼性质(Cassini's identity):\(F_{n-1}\times F_{n+1} - F_n^2\ = (-1)^n\)
- 附加性质:\(F_n+k \ = \ F_k F_{n+1} + F_{k-1}F_n\)
- GCD 性质:\((F_m,F_n) \ = \ F_{(m,n)}\)
八、费马小定理求逆元¶
8.1 费马小定理¶
若P为质数,\(GCD(a,p) = 1\),则\(a^{p-1} ≡ 1 \ (mod \ p)\)
换句话说:对于任意整数a,有\(a^p = a \ (mod \ p)\)
8.2 逆元¶
8.2.1 简介¶
如果一个线性同余方程\(ax ≡ 1 \ (mod \ p)\),则x被称作为\(a \ mod \ p\)的逆元,记作\(a^{-1}\)
8.2.2 如何求¶
有两种方法 扩展欧几里得法 和 快速幂法
我们这里只介绍快速幂的方法:
用到了上面的前置知识:费马小定理
由上面可得:a的乘法逆元为\(a^{p-2}\)
九、训练题单¶
http://acm.mangata.ltd/training/61d167fb9583df9f1d5e39f2