数论入门

CLJ大神保佑oier · 2019-01-09 19:03:24 · 个人记录

数论入门

整除

若 a|b 且 b|c，则a|c

唯一分解定理

正整数的质因数分解是唯一的

正整数除法，就是把两个数的质因数分解，然后每个质数的指数相减

若m|n，则当且仅当：a_1 >= b_1,a_2>=b_2

约数与倍数

约束个数通过质因数分解解决，d=(r_1+1)(r_2 + 1)(r_3+1)……

最大公约数

gcd(n,m)=gcd(m,n \space MOD \space m)

gcd(n,m)=2^{min(a_1,b_1)}+3^{min(a_2,b_2)}+5^{min(a_3,b_3)}

lcm(n,m)=2^{max(a_1,b_1)}+3^{max(a_2,b_2)}+5^{max(a_3,b_3)}

gcd(n,m) \cdot lcm(n,m) = <a_i+b_i> = n\cdot m

模　

两个符号
- 上取整 ceil()
- 下取整 floor() $$
随时取模
- 可证：各位数字之和能被3整除则该数能被3整除
- 可证：最后两位数能被4整除则该数能被4整除

(a+b)mod\ p=(a\ mod\ p+b\ mod\ p)mod\ p

(a\times b)mod\ p=(a\ mod\ p \times b\ mod\ p)mod\ p

模意义
- 36\equiv11(mod5)

a+c\equiv b+c (mod\ p)

a\cdot c\equiv b\cdot c (mod\ p)

模环
奇怪的性质

\lfloor\frac{\lfloor\frac{a}{b}\rfloor}{c}\rfloor= \lfloor{\frac{a}{bc}}\rfloor

gcd(a,b)=gcd(b,a\ mod\ b)

lcm=a/gcd(a,b)*b

典型的质数：19260817

质数

一个整数无非平凡因子

质数定理
- \lim_{n\rightarrow+\infty}\frac{\pi(n)}{\ln n}=1

逆元

x\cdot inv(x) \equiv 1 (mod\ p)

费马小定理： n^{p-1} \equiv 1 (mod\ p)

模质数意义下的逆元求法：inv(x)=x^{p-2}\ mod\ p

常用技巧

存A数组，为i!在mod p意义下的值

存B数组，为inv(i!)在mod p意义下的值

C_n^m=A[n]\times B[m] \times B[n-m]

A[0]=1;
for(int i=1;i<=10;i++)
    A[i]=A[i-1]*i%p;
inv[0]=inv[1]=1;
for(int i=1;i<=10;i++)
    inv[i]=(p-p/i)*inv[p%i]%p;

B[0]=1;
for(int i=1;i<=10;i++)
    B[i]=B[i-1]*inv[i]%p;