OceanEye's Blog

是时候表演真正的技术了!

@OceanEye2周前

08/7
16:03
OI

Miller_Rabin 素数判定

0x00

Miller_Rabin 素数判定
为什么要写这个……因为我把它忘掉了
于是写篇文章复习复习……

0x01

基础知识:

费马小定理

\(a^{n-1} \equiv 1\pmod n\)

伪素数

如果n是一个正整数,如果存在和n互素的正整数a满足 \( a^{n-1} \equiv 1\pmod n\),我们说n是基于a的伪素数。如果一个数是伪素数,那么它是素数的可能性很大

Miller-Rabin测试

不断选取不超过\(n-1\)的基\(b\)(\(s\)次),计算是否每次都有\( b^{n-1} \equiv 1\pmod n\),若每次都成立则n是素数,否则为合数。

快速幂

这是基础知识……

快速乘

快速乘是在模意义下的乘法
具体来说就是a*b%c超出限制的时候用的 , 用了位运算的技巧
代码如下

0x02

上面有了伪素数的定义……那么我们可以用一些朴素的方法来验证素数
比如……我们随机几个数然后跑跑

大概每次筛正确的概率是 \( frac{3}{4} \)

0x03

然后讲一个不是那么的平凡的优化
因为 \( a^{n-1} \equiv 1\pmod n\)
所以 \( a^{frac{n-1}{2}} \equiv 1 \pmod n\) 或者 \(a^{frac{n-1}{2}} \equiv 1\pmod n\)
如果使用的话可以提高该算法的效率

参考以下的代码

Miller_Rabin 素数判定

@OceanEye2月前

06/17
21:52
OI

BZOJ3098

生日攻击
请手动google
代码

BZOJ3098

@OceanEye3月前

05/24
21:29
OI

BZOJ4591

代码

无脑用Lucas化简   分类后分段递归处理

 

BZOJ4591

@OceanEye3月前

05/24
13:18
OI

BZOJ2982

Lucas定理裸题

恩具体证明请百度 Lucas定理

刚刚发现我是RK3 :-D高兴

 

 

BZOJ2982

@OceanEye3月前

05/21
13:46
OI

FFT—-学习笔记

先上几个好的教程

  1. 某不知名大佬的教程 简直良心治好了我一直没搞清楚的FFT:-D
  2. zky大佬的FFT教程 
  3. kry大佬的板子:-D

[手动分割]

 

UOJ34—-多项式乘法

 

BZOJ2179

 

BZOJ2194

好像就是反过来?

挺裸的:-D

 

 

[代码施工中]

FFT—-学习笔记

@OceanEye4月前

05/3
18:56
OI

BZOJ1419

期望DP
和班上的一个物理大佬一起搞了二十分钟吧……然后发现这个期望(R,B)只和(R-1,B)以及(R,B-1)相关
然后就一个for循环再用一下滚动数组就可以了
dp[r][b]=(dp[r][b-1]-1)*b/(r+b) + (dp[r-1][b]+1)*r/(r+b)

BZOJ1419