第四讲 数学知识
一、质数
(一) 试除法判定质数:O(√n)
bool is_prime(int x){
if(x<2)return false;
for(int i=2;i<=x/i;i++)
if(x%i==0)return false;
return true;
}
(二) 分解质因数:O(√n)
void divide(int n){
for(int i=2;i<=n/i;i++)
if(n%i==0){
int s=0;
while(n%i==0){
n/=i;
s++;
}
printf("%d %d\n",i,s);
}
if(n>1)printf("%d %d\n",n,1);
}
(二) 筛质数
埃氏筛法:O(nloglogn)
int primes[N],cnt;
bool st[N];
void get_primes(int n){
for(int i=2;i<=n;i++){
if(!st[i]){
primes[cnt++]=i;
for(int j=i+i;j<=n;j+=i)st[j]=true;
}
}
}
线性筛法(欧拉筛法):O(n)
int primes[N],cnt;
bool st[N];
void get_primes(int n){
for(int i=2;i<=n;i++){
if(!st[i])primes[cnt++]=i;
for(int j=0;primes[j]*i<=n;j++){
st[i*primes[j]]=true;
if(i%primes[j]==0)break;
}
}
}
二、约数
(一) 试除法求约数:O(√n)
vector<int> get_divivors(int n){
vector<int> res;
for(int i=1;i<=n/i;i++)
if(n%i==0){
res.push_back(i);
if(n/i>i)res.push_back(n/i);
}
sort(res.begin(),res.end());
return res;
}
(二) 约数个数:O(√n)
原理
若 n=∏pαii,则 n 的约数个数为 ∏(αi+1)。
int solve(int n){
unordered_map<int,int> primes;
while(n--){
int x;
cin>>x;
for(int i=2;i<=x/i;i++){
while(x%i==0){
x/=i;
primes[i]++;
}
}
if(x>1)primes[x]++;
}
LL res=1;
for(auto prime:primes)
res=res*(prime.second+1)%mod;
return res;
}
(二) 约数之和:O(√n)
原理
若 n=∏pαii,则 n 的约数之和为 ∏∑αij=0pji。
技巧
计算 ∑αij=0pji 时,可以采用秦九昭算法,
即令 tn=∑nj=0pji,
则 tn=pitn−1+1。
int solve(int n){
unordered_map<int,int> primes;
while(n--){
int x;
cin>>x;
for(int i=2;i<=x/i;i++){
while(x%i==0){
x/=i;
primes[i]++;
}
}
if(x>1)primes[x]++;
}
ll res=1;
for(auto prime:primes){
int p=prime.first,a=prime.second;
ll t=1;
while(a--)t=(t*p+1)%mod;
res=res*t%mod;
}
return res;
}
(三) 最大公约数
欧几里得算法(辗转相除法):O(logn)
原理 \gcd (a,b)=\gcd (b,a \mod b)
int gcd(int a,int b){
return b?gcd(b,a%b):a;
}
三、欧拉函数
定义
1 到 N 中与 N 互质的数个数被称为欧拉函数,记为 \varphi (N)。
(一) 求某个数的欧拉函数:O(\sqrt n)
原理
若 N=\prod p_i^{\alpha _i},
则 \varphi (N)=N\prod\frac{p_i-1}{p_i} =N\prod(1-\frac{1}{p_i})。
int phi(int x){
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);
return res;
}
(二) 筛法求 1 到 n 的欧拉函数:O(n)
原理
若 p 为质数,则 \varphi (p)=p-1;
若 p 为质数且 p \mid i,则 \varphi(pi)=p\varphi(i);
若 p 为质数且 p \nmid i,则\varphi(pi)=\varphi(p)\varphi(i)=(p-1)\varphi(i)。
int primes[N],cnt,phi[N];
bool st[N];
void get_eulers(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[primes[j]*i]=primes[j]*phi[i];
break;
}
phi[primes[j]*i]=(primes[j]-1)*phi[i];
}
}
}
四、快速幂
(一) 快速幂:O(\log n)
int qpow(int a,int k,int p){
int res=1;
while(k){
if(k&1)res=(LL)res*a%p;
k>>=1;
a=(LL)a*a%p;
}
return res;
}
(二) 快速幂求逆元:O(\log n)
原理
欧拉定理
若 \gcd(a,n)=1,则 a^{\varphi(n)} \equiv 1 (\mod n)。
费马小定理
由欧拉定理可得,若 p 为质数,则 a^{p-1}\equiv 1(\mod p)。
由费马小定理可得,当模数 p 为质数时,a^{p-2} 即为 a 模 m 的乘法逆元。
int qpow(int a,int k,int p){
int res=1;
while(k){
if(k&1)res=(LL)res*a%p;
k>>=1;
a=(LL)a*a%p;
}
return res;
}
ans=qpow(a,p-2,p);
五、扩展欧几里得算法
(一) 扩展欧几里得算法:O(\log n)
原理
裴蜀定理
\forall x,y\in \mathbb {N_+},\exists a,b\in \mathbb {Z},s.t. ax+by=\gcd(x,y).
int exgcd(int a,int b,int &x,int &y){
if(!b){
x=1,y=0;
return a;
}
int d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
(二) 线性同余方程:O(\log n)
解方程 ax\equiv b(\mod m)
ax\equiv b(\mod m) m\mid(ax-b) ax-b=my ax+my=b
令 d=\gcd(a,m),由裴蜀定理可知,
若 b\mid d,则可用扩展欧几里得算法计算 x 的值;
若 b\nmid d,则原方程无解。
int exgcd(int a,int b,int &x,int &y){
if(!b){
x=1,y=0;
return a;
}
int d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
int d=exgcd(a,m,x,y);
if(b%d)puts("impossible");
else x=(LL)x*(b/d)%m;
六、中国剩余定理
Learning…
七、高斯消元
Learning…
八、求组合数
(一) 求组合数 I(多组询问):O(n^2)
原理
组合数递推式:C_a^b=C_{a-1}^{b-1}+C_{a-1}^b
int c[N][N];
void init(){
for(int i=0;i<N;i++)
for(int j=0;j<=i;j++)
if(j)c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
else c[i][j]=1;
}
To Be Continue…