type
status
date
slug
summary
tags
category
icon
password
简单数学
快速幂
快速幂
使用位运算快速计算一个数的高次幂;
原理
即是将幂次转化为二进制运算,例如
而
所以,的次幂其中可以转化为二进制形式,进行位运算;
例如转化为
可以看作
矩阵快速幂
素数筛
欧拉筛
板子
欧拉函数
唯一分解定理
对于任意 可以把写成若干质数相乘的形式
即
欧几里得算法
最大公约数
得到的余数辗转相除;
;
若为最大公约数
可得为最大公约数,即为递归式
最小公倍数
扩展欧几里得算法
- 利用欧几里得算法得出不定方程,在时得到特殊解,然后步步回溯算法,得出最初解。
同余
设 是非零整数,称 和 模 同余,记作 , 如果
, 反之记作
中国剩余定理
费马小定理
欧拉定理特例
欧拉定理
- 对于 ,则有
- 更一般有
逆元
- 求解逆元在模的意义下,使得
- 如果模数 是一个质数,我们可以直接使用费马小定理计算
证明:
令
在意义下为
乘上得
求逆元
为的逆元
递推求逆元(模数质数):
卢卡斯定理
计算:
负二项分布
成功的概率为p,需成功进行r 次,失败次数x 次,概率为
- Author:Grimner
- URL:https://tangly1024.com/article/example-5
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!