基础知识

对数

概念

若$a^k=N$则$log_aN=k$,$log_aN$读作以$a$为底$N$的对数,即$a$的多少次方等于$N$。

若$a=e^m$,则$m$为$a$的自然对数,即$\ln a=m$。「$e$为一个常数,约等于2.718282」

运算

$log_a(MN)=log_aM+log_aN$,因为$a^m\times a^n=a^{m+n}$。

$log_a(M/N)=log_aM-log_aN$,因为$\frac{a^m}{a^n}=a^{m-n}$。

$log_aM^n=nlog_aM$,因为$(a^m)^n=a^{mn}$。

换底公式:$log_ab=\frac{log_cb}{log_ca}$。

复数

概念

复数时形如$a+bi$的数,其中$a$和$b$都是实数。复数$a+bi$中,$a$为实部,$b$为虚部,$i$为虚数单位。

当$i$为0时,该复数是实数,否则该复数为虚数。

规定虚数单位$i^2=-1$

运算

$(a+bi)\pm (c+di)=(a\pm c)+(b\pm d)i$

$(a+bi)(c+di)=ac+adi+bic+bidi=ac+adi+bci-bd=(ac-bd)+(bc+ad)i$

$\frac{a+bi}{c+di}=\frac{(a+bi)(c-di)}{(c+di)(c-di)}=\frac{(ac+bd)+(bc-ad)i}{c^2-d^2i^2}=\frac{(ac+bd)+(bc-ad)i}{c^2+d^2}$

数论

素数

素数判定

1
2
3
4
5
6
7
inline bool is_prime(int num) {
if(num==2) return true;
for(int i=2;i*i<=num;++i) {
if(num%i==0) return false;
}
return true;
}

线性筛素数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int v[100000005];//存放i的最小质因子
int prime[6000000],idx=0;//存放得到的质数
inline void getPrime(int n) {
memset(v,0,sizeof(v));idx=0;
for(int i=2;i<=n;++i) {//从2开始枚举每个数
if(!v[i]) {//该数是质数
v[i]=i;//最小质因子是它本身
prime[idx++]=i;//加入质数表
}
for(int j=0;j<idx;++j) {//给i乘上一个质数
if(v[i]<prime[j]||i*prime[j]>n) break;//如果最小质因子比当前质数小,相乘后超过范围则退出
v[i*prime[j]]=prime[j];//i*prime[j]的最小质因子是prime[j]
}
}
}

实测找$10^8$以内的质数5761455个,用时0.925212s(环境:2.3 GHz Intel Core i5)。

分解质因数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int p[100000005],c[100000005],idx=0;
bool is_prime(int num) {
if(num==2) return true;
for(int i=2;i*i<=num;++i) {
if(num%i==0) return false;
}
return true;
}
void divide(int num) {
idx=0;
for(int i=2;i*i<=num;++i) {
if(num%i==0) {
c[idx]=0;
while(num%i==0) {
num/=i;
c[idx]++;
}
p[idx++]=i;
printf("%d\n",num);
if(num==1) return;
}
}
if(is_prime(num)) {
c[idx]=1;p[idx++]=num;
}
}

优化了一下(慎用memset),实测分解$10^8$需要0.001676s(环境:2.3 GHz Intel Core i5)。

欧拉函数