type
status
date
slug
summary
tags
category
icon
password
😀
简单数学
 

快速幂

快速幂 使用位运算快速计算一个数的高次幂;
原理
即是将幂次转化为二进制运算,例如
所以,次幂其中可以转化为二进制形式,进行位运算; 例如转化为 可以看作

矩阵快速幂

 

素数筛

欧拉筛 板子

欧拉函数

唯一分解定理

对于任意 可以把写成若干质数相乘的形式

欧几里得算法

最大公约数
得到的余数辗转相除;
;
为最大公约数
可得为最大公约数,即为递归式
最小公倍数

扩展欧几里得算法

  • 利用欧几里得算法得出不定方程,在时得到特殊解,然后步步回溯算法,得出最初解。
 

同余

是非零整数,称 同余,记作 , 如果 , 反之记作
 

中国剩余定理

费马小定理

欧拉定理特例

欧拉定理

  • 对于 ,则有
  • 更一般有

逆元

  • 求解逆元在模的意义下,使得
  • 如果模数 是一个质数,我们可以直接使用费马小定理计算
证明:意义下为
乘上
 
求逆元
的逆元
 
递推求逆元(模数质数):

卢卡斯定理

证明在网上一搜就找得到
计算

负二项分布

成功的概率为p,需成功进行r 次,失败次数x 次,概率为
 
进阶数学可持久化线段树
Announcement
🎉NotionNext 4.1已经上线🎉
-- 感谢您的支持 ---
域名即将迁移到
请及时记录防迷路()