奇怪的数学——写给自己，以防忘记

• 一 组合数
  • 1 和杨辉三角的关系
• 二 逆元
  • 1 快速幂求逆元
• 三 矩阵
  • 1 矩阵乘法
  • 2 矩阵乘法的运算定律
    • 1 不满足交换律
    • 2 满足结合律ABCABC
    • 3 满足分配律ABCACBC ABCABAC
• 四其它奇怪东西
  • 1如果有互质数ab不能表示成axby的数最大为ab-a-b

一、 组合数

C(m,n)表示m个中选n个的方案数

C(m,n)&＃61;m!n!(m−n)!

1、 和杨辉三角的关系

C(i,0)&＃61;C(i,i)&＃61;1

C(i,j)&＃61;C(i−1,j−1)&＃43;C(i−1,j)

这就是杨辉三角&＃xff1a;

0 1 2 3 4
0|1
1|1 1
2|1 2 1
3|1 3 3 1
4|1 4 6 4 1
……

二、 逆元

对于a和模数p&＃xff0c;若ax≡1(modp)&＃xff0c;则x是a的逆元。
有什么用&＃xff1f;当你要除以a时&＃xff0c;你可以用乘x代替。因为除法不能直接进行模运算。
举个例子&＃xff1a;
a&＃61;2 p&＃61;7
则x&＃61;4
当我们要算6/2 mod 7时&＃xff0c;可以用6*4 mod 7来代替。

1、 快速幂求逆元

有一个奇怪的公式&＃xff1a;

aφ(p)≡1(modp)

变形得&＃xff1a;

a∗aφ(p)−1≡1(modp)

所以aφ(p)−1即a的逆元。
当p为质数时&＃xff0c;φ(p)&＃61;p-1。模数常常是质数。所以ap−2就是a的逆元&＃xff08;重复一遍&＃xff0c;p为质数时&＃xff01;&＃xff09;

三、 矩阵

加减不说&＃xff0c;对应的加在一起好了。

1、 矩阵乘法

一张好图&＃xff0c;在这里发现的&＃xff0c;方便理解矩阵乘法。(这张图是从0开始的&＃xff0c;我们习惯从1开始)

一个m∗n的的A矩阵&＃xff0c;和一个n∗p的B矩阵相乘&＃xff0c;将得到一个m∗p的矩阵C

C(i,j)&＃61;∑k&＃61;1pA(i,k)∗B(k,j)

可以简单地理解为&＃xff0c;A中i行的元素&＃xff0c;与B中j列的元素&＃xff0c;对应相乘得到的和。

2、 矩阵乘法的运算定律

&＃xff08;1&＃xff09; 不满足交换律

&＃xff08;2&＃xff09; 满足结合律&＃xff1a;(AB)C&＃61;A(BC)

&＃xff08;3&＃xff09; 满足分配律&＃xff1a;(A&＃43;B)C&＃61;AC&＃43;BC A(B&＃43;C)&＃61;AB&＃43;AC

四、其它奇怪东西

1、如果有互质数a,b&＃xff0c;不能表示成ax&＃43;by的数最大为ab−a−b