质数筛
线性筛法：
保证每个数都被其最小质因数给筛掉。
代码：
void solve()
{
for(int i=2;i<=n;i++){
if(!st[i])primes[++tot]=i;
for(int j=1;j<=tot;j++){
st[i*primes[j]]=true;
if(i%primes[j]==0)break;//i的最小质因子为primes[j]
}
}
}
素性测试
判定\(x\)是否为质数
1.朴素方法：
复杂度\(O(\sqrt n)\)
代码：
for(int i=2;i<=n/i;i++){
if(n%i==0)return false;
}
retrun true;
2.\(Miller Rabin\) 算法
给出一个奇素数\(p\)，则\(p-1\)为偶数，设\(p-1=m\times 2^q\).
由费马小定理，\(a^{p-1}\equiv a^{m\times 2^q}\equiv 1(\bmod\) \(p)\)
\(a^{m\times 2^q}\equiv a^{(m\times 2^{q-1})^2}\equiv 1 (\bmod\) \(p)\)
所以\(a^{m\times 2^k}\equiv 1||(p-1)(\bmod\) \(p)(k\in Z,0\leq k< q)\)
则：
1.从\(0\)~\(q-1\)枚举\(k\)检验其是否满足\(a^{m\times 2^k}\equiv 1||-1(\bmod\) $ p)$
2.检验\(p\)是否满足费马小定理\(a^{p-1}\equiv 1(\bmod\) \(p)\)
可进行\(k\)轮检测，取不同的值\(a\)，出错率为\(4^{-k}\)
时间复杂度：\(O(k\log n)\)
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL q_c(LL x,LL y,LL p) //快速乘 ,避免爆long long
{
LL res=0;
while(y){
if(y&1)res=(res+x)%p;
x=(x+x)%p;
y>>=1;
}
return res;
}
LL q_m(LL x,LL y,LL p)//快速幂
{
LL res=1;
while(y){
if(y&1)res=q_c(res,x,p);
x=q_c(x,x,p);
y>>=1;
}
return res;
}
bool miller_rebin(LL n)//判断n是否为质数
{
if(n==2)return true;//特判
if(n<2||n%2==0)return false;
LL u=n-1,tt=0;
while(u%2==0)u/=2,tt++;//求出q、m
for(int i=0;i<10;i++){
LL a=rand()%(n-1)+1;//在1~n-1随机取值
LL x=q_m(a,u,n);
if(x==1)continue;
for(int j=1;j<=tt;j++){
LL y=q_c(x,x,n);//相当于依次枚举k
if(y==1&&x!=1&&x!=n-1)return false;
x=y;
}
if(x!=1)return false;//费马小定理（最后x的值为a^n-1 % n）
}
return true;
}
int main()
{
int n;
cin>>n;
while(n--){
LL a;
cin>>a;
if(miller_rebin(a))puts("Yes");
else puts("No");
}
return 0;
}
威尔逊定理
若\(p\)为质数，则$(p-1)!\equiv -1(\bmod $ \(p)\)
反之，若$(p-1)!\equiv -1(\bmod $ \(p)\)，则\(p\)为质数
证明：
——————
唯一分解定理
任意正整数\(n\)可以写成 \(n=2^{a1}*3^{a2}*5^{a3}*…\) ,其中\(a1,a2,a3\)等为非负整数
证明：
——————
可整除性的基本性质
若 \(a|b\) , \(a|c\) 则 \(a|(b+c)\)
若 \(a|b\) 则对任何整数 \(c\) 满足 \(a|bc\)
若 \(a|b\) , \(b|a\), 则 \(a|c\) (传递性)
gcd和lcm
定理：\(x\times y=\gcd(x,y)\times \operatorname{lcm}(x,y)\)
证明：
由唯一分解定理：
设集合\(A\)为\(x\)的质因子，集合\(B\)为\(y\)的质因子
\(\gcd(x,y)=p_1^{\min(a_1,b_1)}\times p_2^{\min(a_2,b_2)}\times ...\times p_n^{\min(a_n,b_n)}(p_i\in A\cap B)\)
\(\operatorname{lcm}(x,y)=p_1^{\max(a_1,b_1)}\times p_2^{\max(a_2,b_2)}\times ...\times p_n^{\max(a_n,b_n)}(p_i\in A\cap B) \times q_1^{c_1}\times q_2^{c_2}\times ...\times q_m^{c_m}(q_i\in A \cup B,q_i \notin A \cap B)\)
即可得证
取模运算基本性质：（有效防止爆long long）
\((a+b)\bmod m=(a\bmod m+b\bmod m)\bmod m\)
\((a-b)\bmod m=(a\bmod m-b\bmod m)\bmod m\)
\((a*b)\bmod m=(a\bmod m*b\bmod m)\bmod m\)
除法不能满足上述性质，但是：
设 \(z\) 为 \(y\) 模 \(m\) 的逆元，则 \((x/y)\bmod m=(x\bmod m*z\bmod m)\bmod m\)
欧几里得算法
利用公式 \(\gcd(a,b)=\gcd(b,a\bmod b)\) , 复杂度为\(O(\log b)\)
代码
int gcd(int a,int b)
{
return b? gcd(b,a%b):a;
}
辗转相减法（更相减损术）:(似乎用来处理高精度）
——————
拓展欧几里得
裴蜀定理：对于不完全为0的非负整数 \(a,b\) ,必然存在整数对 \(x,y\) ,使得 \(\gcd(a,b)=ax+by\) 。
证明：
——————
代码：
设\(x,y\)和\(x_1,y_1\)是两组解，且满足：
\(\gcd(a,b)=ax+by\)
\(gcd(a,b)=gcd(b,a\bmod b)=bx_1+a\bmod b*y_1\)
则 \(ax+by=bx_1+a\bmod b*y_1\)
设 \(k=a/b,r=a\bmod b\) ,则：
\(bk+r=a\)
\(ax+by=bx_1+ry_1=bx_1+(a-bk)y_1=bx_1+(a-a/b*b)y_1\)
\(ax+by=ay_1+b(x_1-a/b*y_1)\)
所以 \(x=y_1,y=x_1-a/b*y_1\)
#include<bits/stdc++.h>
using namespace std;
int exgcd(int a,int b,int &x,int &y)//&不能漏
{
if(!b){
x=1,y=0;
return a;
}
int res=exgcd(a,b,x,y);
int t=x;x=y;y=t-a/b*y;
return res;
}
int main()
{
return 0;
}
应用：
解不定方程\(ax+by=c\)
先用\(exgcd\)求出\(ax+by=\gcd(a,b)\)的解\(x_0,y_0\)
设\(\gcd(a,b)=d\)
若 $c\bmod d \ne 0 $则方程无解
方程的一组解为\(x_1=x_0c/d,y_1=y_0c/d\)
方程的一般解\(x=x_1+bk/d,y=y_1-ak/d(k\in Z)\)
求解线性同余方程
对于\(ax\equiv b(\bmod m)(a,b,m\)为常数\()\)
可转化为\(ax=b+my\) 解不定方程
求解模的逆元
\(ax\equiv 1(\bmod m)(a,m\)为常数\()\)
解线性同余方程:
\(ax-my=1\)
设\(d=\gcd(a,-m)\)
若要求\(x\geq0\)的最小解\(x_1\)：
个人方法：
假设求得一个解为\(x\)
设\(k=x\times d/(-m)\)
\(x_1=x+k*(-m)/d\)
若\(x_1<0\)则\(x_1=x_1+|(-m)\times d|\)
——————