数论基础 | 洛灵酱的小窝

洛灵酱的小窝

闻道有先后,术业有专攻。

0%

数论基础

最大公约数

gcd(a, b) = gcd(b, a % b)

1
2
3
4
5
6
7
8
9
int gcd(int a, int b) {
int mod;
while(b > 0) {
mod = a % b;
a = b;
b = mod;
}
return a;
}

最小公倍数

1
2
3
int lcm(int a, b) {
return a * b / gcd(a, b);
}

互质数

互质数为数学中的一种概念,即两个或多个整数的公因数只有1的非零自然数。公因数只有1的两个非零自然数,叫做互质数。

基本不等式

a+b2aba+b \geq 2 \sqrt{ab}

算数基本定理

任何一个大于1的正整数都能唯一分解成有限个质数的乘积,可以写作:

N=p1c1p2c2p3c3pmcmN = p_1^{c_1}p_2^{c_2}p_3^{c_3} \cdots p_m^{c_m}

其中p1,p2,p3pip_1,p_2,p_3 \cdots p_i都是质数且递增,cic_i都是正整数。

基本算数定理的推论

  • NN的正整数合集为p1b1p2b2p3b3pmbmp_1^{b_1}p_2^{b_2}p_3^{b_3} \cdots p_m^{b_m},其中0bici0 \leq b_i \leq c_i

  • NN的正约数个数为i=1m(ci+1)\prod^m_{i=1}(c_i+1)

  • NN的所有正约数的和为(1+p1+p12++p1c1)××((1+pm+pm2++pmc1)=m=1m(j=0ci(pm)j)(1+p_1+{p_1}^2+ \cdots +{p_1}^{c_1}) \times \cdots \times ((1+p_m+{p_m}^2+ \cdots +{p_m}^{c_1}) = \prod^m_{m=1}(\sum^{c_i}_{j=0}(p_m)^j)

欧拉函数

两个数的gcd等于11,即两个数互质。

11nn中与nn互质的数的个数成为欧拉函数记ϕ(n)\phi(n)

ϕ(n)=N×p11p1×p21p2××pm1pm\phi(n) = N \times \frac{p^1-1}{p^1} \times \frac{p^2-1}{p^2} \times \cdots \times \frac{p^m-1}{p^m}

同余

若整数aa和整数bb除以正整数mm的余数相等,则称为aabbmm余数相同,则称为aabbmm同余,记为ab(modm)a \equiv b\pmod m

同余满足反身性、对称性、传递性。

  • aa(modm)a \equiv a\pmod m

  • ab(modm)a \equiv b\pmod m,则ba(modm)b \equiv a\pmod m

  • ab(modm)a \equiv b\pmod mbc(modm)b \equiv c\pmod m,则ac(modm)a \equiv c\pmod m

翡翠定理

又称贝祖公式,指的是当ax+by=max+by=m有整数解时,只有mmaabb最大公约数dd的倍数。
翡翠等式有解时必然有无穷多个整数解,每组解xxyy都成为翡翠数,可以使用扩展欧几里得算法求得。

扩展欧几里得算法

已知整数aabb,扩展欧几里得算法可以在求得aabb的最大公约数的同时,找到整数xxyy(其中一个很可能是负数),使它们满足翡翠等式ax+by=gcd(a,b)ax+by=gcd(a,b)
如果aa是负数,可以把问题转化成a(x)+by=gcd(a,b)|a|(-x)+by=gcd(|a|,b),然后令x=(x)x'=(-x)

1
2
3
4
5
6
7
8
9
void exgcd(ll a, ll b, ll &x, ll &y) {
if (b == 0) {
x = 1, y = 0;
return;
}

exgcd(b, a % b, y, x);
y -= (a / b) * x;
}

斐波那契数列

f(1)=1f(1) = 1

f(2)=1f(2) = 1

f(3)=f(1)+f(2)=f(32)+f(31)f(3) = f(1) + f(2) = f(3-2) + f(3-1)

f(n)=f(n2)+f(n1)f(n) = f(n-2) + f(n-1)

卡特兰数

f(0)=1f(0) = 1

f(1)=1f(1) = 1

f(n)=f(0)×f(n1)+f(1)×f(n2)+f(n)×f(0)f(n) = f(0) \times f(n-1) + f(1) \times f(n-2) \cdots + f(n) \times f(0)

应用:长度为n的栈一共有多少种出栈的方法。