数学部分学习-个人在线分享-虚灵IT资料分享

1、欧拉函数

计算单个值的欧拉函数
- 基于公式：$phi(n) = n* \frac{p_1-1}{p_1} * \frac{p_2-1}{p_2}*\dots *\frac{p_n-1}{p_n} $其中p_i 为为为n$的质因数。$
- 写代码用试除法可以快速求解

筛法求欧拉函数（线性筛）

代码如下：

for i in range(2,n+1):
    if st[i]==0:
        primes.append(i)
        phi[i]=i-1 # 质数的phi(i)=i-1
    for j in range(len(primes)):
        if primes[j]*i>n:break
        st[primes[j]*i]=1
        if i%primes[j]==0:
            phi[i*primes[j]] = phi[i]*primes[j] # primes[j]是i的质因素数
            break
        phi[i*primes[j]] = phi[i]*(primes[j]-1) # primes[j]不是i的质因数

欧拉降幂
- 基本公式
  $a^b \equiv \begin{cases} a^{b \ mod \ \varphi(m)}, \ \ \ \ \ \ \ \ \ \ \ \ \ gcd(a,m)=1, \ a^b, \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ gcd(a,m) ot=1,b<\varphi(m),\ \ \ \ (mod \ \ m)\ a^{(b \ mod \ \varphi(m)) + \varphi(m)}, \ \ gcd(a,m) ot =1,b\ge \varphi(m). \end{cases} ab≡⎩ ⎨ ⎧ab mod φ(m), gcd(a,m)=1,ab, gcd(a,m)=1,b<φ(m), (mod m)a(b mod φ(m))+φ(m), gcd(a,m)=1,b≥φ(m).$

2、乘法逆元

费马小定理求逆元

扩展欧几里得算法求逆元

如果求得最大公约数不是1则无解，否则逆元就是

def exgcd(a,b,x,y):
    if b==0:
        return a,1,0
    d,x,y = exgcd(b,a%b,x,y)
    x,y = y,x-a//b*y
    return d,x,y

3、中国剩余定理

C
R
T
CRT
$CRT$ 中国剩余定理基本形式
- 中国剩余定理给出了以下的一元线性同余方程组的解：
{
x
≡
a
1
(
m
o
d
m
1
)
x
≡
a
2
(
m
o
d
m
2
)
⋮
x
≡
a
n
(
m
o
d
m
n
)
\begin{cases} x \equiv a_1 \pmod{m_1} \ x \equiv a_2 \pmod{m_2} \ \qquad \vdots \ x \equiv a_n \pmod{m_n} \end{cases}
$⎩$
⎨
⎧x≡a1(modm1)x≡a2(modm2)⋮x≡an(modmn)
- 在中国剩余定理中： $a_1, a_2, \ldots, a_n a1,a2,…,an 是给定的余数， m 1 , m 2 , … , m n m_1,m_2,\ldots,m_n m1,m2,…,mn两两互质，如果两两不互质则是扩展中国剩余定理。$
C
R
T
CRT
$CRT$ 问题的解决方法
- CRT主要利用
  m
  1
  ,
  m
  2
  ,
  …
  ,
  m
  n
  m_1,m_2,\dots,m_n
  $m_{1}, m_{2}, \dots, m_{n}$ 为两两互质的整数的性质。我们可以令：
  
  M
  =
  m
  1
  ×
  m
  2
  ×
  ⋯
  ×
  m
  n
  =
  ∏
  i
  =
  1
  n
  m
  i
  M
  i
  =
  M
  /
  m
  i
  M=m_1 imes m_2 imes \dots imes m_n = \begin{equation} \prod_{i=1}^{n}m_i \end{equation}\ M_i = M/m_i
  $M = m_{1} \times m_{2} \times \dots \times m_{n} = i = 1 \prod n m_{i} M_{i} = M / m_{i}$
  明显这里的
  M
  i
  M_i
  $M_{i}$ 是和
  m
  i
  m_i
  $m_{i}$ 互质的。
- 接着我们定义逆元：
  
  t
  i
  =
  M
  i
  −
  1
  t_i = M_i^{-1}
  $t_{i} = M_{i - 1}$
- 所以我们可以构造出一个解
  x
  0
  x_0
  $x_{0}$
  
  x
  0
  =
  ∑
  i
  =
  1
  n
  a
  i
  M
  i
  t
  i
  x_0 = \sum_{i=1}^{n}a_iM_it_i
  $x_{0} = i = 1 \sum n a_{i} M_{i} t_{i}$
- 解释
  ∀
  j
  ∈
  [
  1
  ,
  n
  ]
  \forall j \in [1,n]
  $\forall j \in [1, n]$ ：
  
  {
  a
  j
  M
  j
  t
  j
  %
  m
  i
  =
  0
  
  j
  ≠
  i
  a
  j
  M
  j
  t
  j
  %
  m
  i
  =
  a
  i
  
  j
  =
  i
  \begin{cases} a_jM_jt_j \% m_i = 0 \ \ \ \ \ \ j
  eq i \ a_jM_jt_j \% m_i = a_i \ \ \ \ \ j=i \end{cases}
  ${a_{j} M_{j} t_{j} % m_{i} = 0 j \neq = i a_{j} M_{j} t_{j} % m_{i} = a_{i} j = i$
- 通解就是
  x
  =
  x
  0
  +
  k
  M
  x = x_0 + kM
  $x = x_{0} + k M$ ，而CRT问题所求的最小整数解其实就是
  a
  n
  s
  =
  x
  %
  M
  ans = x \% M
  $an s = x % M$
E
X
C
R
T
EXCRT
$EXCRT$ 扩展中国剩余定理的基本用法性质
- 同余方程合并后模数是原来模数的最小公倍数。
- 合并的流程：
  - 假设前
    k
    −
    1
    k-1
    $k - 1$ 个同余方程合并得到新的方程为：
    x
    =
    r
    1
    (
    m
    o
    d
    M
    )
    x = r_1 \pmod{M}
    $x = r_{1} (mod M)$ ，
    M
    M
    $M$ 是前
    k
    −
    1
    k-1
    $k - 1$ 个同余方程模数的最小公倍数，现在需要考虑合并第
    k
    k
    $k$ 个方程：
    x
    =
    r
    2
    (
    m
    o
    d
    m
    k
    )
    x = r_2 \pmod{m_k}
    $x = r_{2} (mod m_{k})$ 。
  - 对于前
    k
    −
    1
    k-1
    $k - 1$ 个同余方程，其通解为
    x
    =
    r
    1
    +
    i
    ∗
    M
    ,
    i
    ∈
    Z
    x=r_1+i*M,i \in Z
    $x = r_{1} + i * M, i \in Z$ ，接着在通解里面找到一个
    t
    t
    $t$ ，使得
    (
    r
    1
    +
    t
    ∗
    M
    )
    %
    m
    k
    =
    r
    2
    (r_1+t*M) \%m_k=r_2
    $(r_{1} + t * M) % m_{k} = r_{2}$ ，即可满足第
    k
    k
    $k$ 个方程。那么合并后前
    k
    k
    $k$ 个同余方程的通解就是
    
    x
    =
    r
    1
    +
    t
    ∗
    M
    +
    i
    ∗
    l
    c
    m
    (
    M
    ,
    m
    k
    )
    ,
    
    i
    ∈
    Z
    x = r_1 + t*M + i* lcm(M,m_k), \ i \in Z
    $x = r_{1} + t * M + i * l c m (M, m_{k}), i \in Z$
    再对通解模
    l
    c
    m
    (
    M
    ,
    m
    k
    )
    lcm(M,m_k)
    $l c m (M, m_{k})$ 即可得到新的
    a
    n
    s
    ans
    $an s$ 作为前
    k
    k
    $k$ 个同余方程的最小整数解。
  - 其中找
    t
    t
    $t$ 的过程：
    M
    ∗
    t
    +
    m
    k
    ∗
    y
    =
    r
    2
    −
    r
    1
    M*t + m_k*y=r_2-r_1
    $M * t + m_{k} * y = r_{2} - r_{1}$ ，其中
    M
    M
    $M$ 就是裴蜀等式的
    a
    ,
    t
    a,t
    $a, t$ 就是裴蜀等式的
    x
    x
    $x$ ，其中
    r
    2
    −
    r
    1
    r_2-r_1
    $r_{2} - r_{1}$ 要满足
    g
    c
    d
    (
    M
    ,
    m
    k
    )
    ∣
    (
    r
    2
    −
    r
    1
    )
    gcd(M,m_k)|(r_2-r_1)
    $g c d (M, m_{k}) ∣ (r_{2} - r_{1})$ ，否则无解。
  - 我们先用扩展欧几里得求解出
    M
    ∗
    t
    +
    m
    k
    ∗
    y
    =
    g
    c
    d
    (
    M
    ,
    m
    k
    )
    M*t + m_k*y=gcd(M,m_k)
    $M * t + m_{k} * y = g c d (M, m_{k})$ ，顺便求出
    g
    c
    d
    (
    M
    ,
    m
    k
    )
    gcd(M,m_k)
    $g c d (M, m_{k})$ ，再将得到的解
    t
    =
    t
    ∗
    r
    2
    −
    r
    1
    g
    c
    d
    (
    M
    ,
    m
    k
    )
    t = t* \frac{r_2-r_1}{gcd(M,m_k)}
    $t = t * \frac{r _{2} - r _{1}}{g c d ( M , m _{k} )}$ ，即可求得
    t
    t
    $t$ 。

4、组合数

方法一：利用递推公式：
c
[
a
]
[
b
]
=
c
[
a
−
1
]
[
b
]
+
c
[
a
−
1
]
[
b
−
1
]
c[a][b] = c[a-1][b]+c[a-1][b-1]
$c [a] [b] = c [a - 1] [b] + c [a - 1] [b - 1]$ 即考虑当前选不选的问题。
O
(
n
2
)
O(n^2)
$O (n^{2})$ 其中(
n
≤
2000
n \le 2000
$n \leq 2000$ )
方法二：预处理逆元法：根据公式计算：
C
a
b
=
a
!
(
a
−
b
)
!
b
!
C_a^{b} = \frac{a!}{(a-b)!b!}
$C_{a b} = \frac{a !}{( a - b )! b !}$ 由于后面数值一般很大会设置一个模数，可以考虑计算出
f
a
c
[
i
]
fac[i]
$f a c [i]$ 表示
i
i
$i$ 的阶乘，
i
n
f
a
c
[
i
]
infac[i]
$in f a c [i]$ 表示
i
i
$i$ 的阶乘的逆元。因此：
C
a
b
=
f
a
c
[
a
]
∗
i
n
f
a
c
[
a
−
b
]
%
p
∗
i
n
f
a
c
[
b
]
%
p
C_a^{b}=fac[a]*infac[a-b]\%p*infac[b]\%p
$C_{a b} = f a c [a] * in f a c [a - b] % p * in f a c [b] % p$ .此方法可以预处理出$n \le 1e5 $的数。
方法三：利用
L
u
c
a
s
Lucas
$Lu c a s$ 定理：
C
a
b
=
C
a
%
p
b
%
p
∗
C
a
/
/
p
b
/
/
p

(
m
o
d

p
)
C_a^{b}=C_{a\%p}^{b\%p}*C_{a//p}^{b//p}\ (mod \ p)
$C_{a b} = C_{a % p b % p} * C_{a // p b // p} (m o d p)$ 可以处理(
1
≤
b
≤
a
≤
1
0
18
1 \le b \le a \le10^{18}
$1 \leq b \leq a \leq 1 0^{18}$ ，
p
p
$p$ 为质数)
```
def lucas(a,b,p):
	if a<p and b<p:return C(a,b,p)
	return C(a%p,b%p,p)*lucas(a//p,b//p,p)%p
```
- 应用：括号序列(
  C
  2
  n
  n
  −
  C
  2
  n
  n
  −
  1
  C_{2n}^{n}-C_{2n}^{n-1}
  $C_{2 n n} - C_{2 n n - 1}$ )，这个也称为卡特兰数（合法出栈数）
  卡特兰数公式： $f(n)=\frac{C_{2n}^{n}}{n+1}=C_{2n}^{n}-C_{2n}^{n-1} f(n)=n+1C2nn=C2nn−C2nn−1$

5、容斥原理

二项式反演：
- 恰好和至少的转换（常用到）
  - 设 $f_i fi表示至少有 k k k个的方案数， g i g_i gi表示恰好有 k k k个方案数，则有：$
  f
  k
  =
  ∑
  i
  =
  k
  n
  (
  n
  k
  )
  g
  i
  f_k=\sum_{i=k}^{n} \binom{n}{k}g_i
  $f_{k} = i = k \sum n (k n) g_{i}$
  - 根据二项式反演则有：
  g
  k
  =
  ∑
  i
  =
  k
  n
  (
  −
  1
  )
  i
  −
  k
  (
  i
  k
  )
  f
  i
  g_k=\sum_{i=k}^{n}(-1)^{i-k} \binom{i}{k}f_i
  $g_{k} = i = k \sum n (- 1)^{i - k} (k i) f_{i}$
  - 当我们需要求恰好
- 恰好和至多的转换（没上面常用）
  - 设 $f_i fi表示至多有 k k k个方案数， g i g_i gi表示恰好有 k k k个方案数，则有：$
  f
  k
  =
  ∑
  i
  =
  0
  n
  (
  n
  k
  )
  g
  i
  f_k=\sum_{i=0}^{n} \binom{n}{k}g_i
  $f_{k} = i = 0 \sum n (k n) g_{i}$
  - 根据二项式反演则有：
  g
  k
  =
  ∑
  i
  =
  0
  n
  (
  −
  1
  )
  k
  −
  i
  (
  i
  k
  )
  f
  i
  g_k=\sum_{i=0}^{n} (-1)^{k-i} \binom{i}{k}f_i
  $g_{k} = i = 0 \sum n (- 1)^{k - i} (k i) f_{i}$
  - 当发现最多有

6、博弈论

四种经典组合游戏
- 尼姆游戏：
  n
  n
  $n$ 堆物品，每堆
  a
  i
  a_i
  $a_{i}$ 个，两名玩家轮流，每次选一堆，至少取1个最多可全部取走。
  结论：令$S=\oplus_{i=1}^n a_i
- 巴什博弈：
  1
  1
  $1$ 堆石子，总数
  n
  n
  $n$ 个，两名玩家轮流取，每次至少取1个，最多取m个，取走最后一个的玩家获胜。
  结论：可以发现不管怎么取都可以操作出
- 威佐夫博弈：
  2
  2
  $2$ 堆石子，石子数可以不同，两名玩家轮流取石子，每次可以从一堆中取或从两堆中取走相同个石子。取走最后一个石子的人获胜。
  结论：设 $x=\frac{1+\sqrt 5}{2} x=21+5 ，则第 i i i个必败态( a i , b i a_i,b_i ai,bi)满足$a_i=\lfloor ix\rfloor , , ,b_i=i+a_i=\lfloor ix^2 \rfloor$.$
  在实际代码中就是 $int(abs(a-b)*\frac{1+\sqrt 5}{2}) min(a,b)=int(abs(a−b)∗21+5 )则先手必败，反之 w i n win win.$
- 斐波那契博弈：
  1
  1
  $1$ 堆石子，总数
  n
  n
  $n$ 个，两名玩家轮流取，先手不能一次取完，至少1个，之后每次可以取的石子数至少为1，至多为对手刚取的石子数的2倍。取走最后一个的获胜。
  结论：当且仅当石子个数为斐波那契数时先手必败。
N
i
m
−
S
G
Nim-SG
$N im - SG$ 函数
- 尼姆游戏的变种总结出来的规律。
  M
  e
  x
  Mex
  $M e x$ 运算：
  m
  e
  x
  (
  S
  )
  =
  min
  ⁡
  {
  x
  ∈
  N
  ∣
  x
  ∉
  S
  }
  {
  x
  }
  mex(S)=\min\limits_{\{x \in \mathbb{N} \mid x
  ot \in S \}} \{x\}
  $m e x (S) = {x \in N ∣ x \neq \in S} min {x}$ 也就是不在
  S
  S
  $S$ 集合中的最小自然数
- S
  G
  SG
  $SG$ 函数计算每一个节点的
  s
  g
  sg
  $s g$ 值，
  S
  G
  (
  x
  )
  =
  m
  e
  x
  (
  {
  S
  G
  (
  y
  1
  )
  ,
  S
  G
  (
  y
  2
  )
  ,
  …
  ,
  S
  G
  (
  y
  k
  )
  }
  )
  SG(x)=mex(\{SG(y_1),SG(y_2),\dots,SG(y_k)\})
  $SG (x) = m e x ({SG (y_{1}), SG (y_{2}), \dots, SG (y_{k})})$ ，其中
  y
  1
  ,
  y
  2
  ,
  …
  ,
  y
  k
  y_1,y_2,\dots,y_k
  $y_{1}, y_{2}, \dots, y_{k}$ 是
  x
  x
  $x$ 的后继节点。
```
def mex(lst):
    lst = list(set(lst))
    return next((idx for idx,num in enumerate(lst) if idx!=num),lst[-1]+1)
def SG(lst,n):
    sg = [0]*(n+5)
    for i in range(1,n+1):
        sg[i] = mex([sg[i-j] for j in lst if i-j>=0])
    return sg
```
- 这个模板基本通用了。

一	二	三	四	五	六	日
				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	27	28	29	30	31

1、欧拉函数

2、乘法逆元

3、中国剩余定理

4、组合数

5、容斥原理

6、博弈论

admin 钻石

相关推荐