Processing math: 100%

[研学] 质因数分解及素性判定

[研学] 质因数分解及素性判定

时间:2018.10 ~ 2019.3

参加成员:Modem_  Lagoon   _Qijia   mnihyc

感觉这个是人生巅峰了, Lagoon 上清华,剩下我们三也退役了,摆在这留作纪念ww  拿濑户口的话来说,就是萌新那会才是最辉煌的时期www

  • 【序言】

质数的研究一直是数学与信息学领域中的重要课题,质数的判定与质因数分解在现代通讯保密领域中更是发挥着重要的作用,本课题小组将通过此次研学机会对不同规模下自然数素性判定及质因数分解的有效算法进行探究,加深对该领域的了解和理解。

 

  • 【1.0】素数的定义

素数,又称质数。一个数 n 是素数当且仅当它是大于 1 的自然数且它的因数有且仅有 1n

 

  • 【1.1】记号与规定

    1. \displaystyle\mathbb{R} 表示实数集,\displaystyle\mathbb{N} 表示自然数集,P 表示素数集。
    2. 勒让德符号 \displaystyle\left( {\frac{n}{p}} \right)。设 \displaystyle p \in P,n \in \mathbb{N}

 

  • 【1.2】素数的一些性质

    • P 是无限集。
    • 对于任意大于 1 的自然数,它要么是个素数,要么可以分解为若干素数之积,并且在忽略顺序的情况下,这样的分解是唯一的。
    • 小于 n 的质数大约有 \ln n 个。
    • 一个合数 n 最小的素因数因数一定小于 \sqrt n
    • 费马小定理:设 p 是大于 2 的素数,则对于任意正整数 n 均有 \displaystyle \begin{array}{*{20}{c}}{{n^{p – 1}} \equiv 1}&{(\bmod p)}\end{array}
    • Mertens’ second theorem

 

  • 【2.0】素性判定

因为素数集为无限集,并且素数的分布没有规律,所以我们需要实现一个算法来判定一个数是否为素数。而素性判定算法正是这样一类算法:输入一个整数,返回这个数是“素数”还是“合数”。…

[研学] 偏序问题的研究

[研学] 偏序问题的研究

时间:2019.04 ~ 2019.09

参加成员:Modem_  Lagoon  _Qijia  mnihyc

备注:第二年就开始混水了啊(笑),只存了自己写的那部分:

  • 高维偏序

至此,k \le 3 的问题已经被我们解决了。

k = 4 呢?CDQ套CDQ?CDQ套树套树?树套树套树?

如果 k 更大,达到 k = 10 呢?十维树状数组?树套树套树套树套………?

很明显 O(n{\log ^{k – 1}}n) 的复杂度是承受不起的,需要从别的方面下手。

注意到在 k 变大的同时,n 也在变小,所以可以考虑复杂度以 n 为主的算法。

首先考虑的,当然是暴力啦)。

可以暴力枚举所有维度,并且按照这个维度(上的数)排序,这些就可以快速找出一个点控制了其它哪一些点。如果把这个信息用一个长度为 n 的二进制数表示,那么对于每个询问,只需要把它在所有维度下的二进制数取“与”运算(即能控制的点取交集),这样答案就是二进制位为 1 的数量了。

维护二进制串?当然是用 std::bitset<>  啦)。

这样复杂度就是 \displaystyle O\left( {\frac{{{n^2}k}}{{32}}} \right) ,足以通过本题了。

 

代码略。

 

这里其实还有一种在时空复杂度上的优化——分块)。

按照分块的那一套理论,把区间分成 \sqrt n 个,每块用一个 std::bitset<>  维护前缀,同时维护一个块最大值。查询的时候在块上二分,找到询问点所在的块,然后暴力加块内的点即可。时间复杂度即可缩小至 \displaystyle O\left( {\frac{{nk\sqrt n }}{{32}}} \right)

 

 …

CSP-S 2019 退役游记 && 破百纪念

现在时间 UTC+8 18:18 2019/11/15,距 CSP-S 2019 还有约 14 个小时。

是时候,准备离开机房了。

(刚好也是本 blog100 篇文章,顺便纪念一下www

 …

浅谈斜率优化——截距优化

浅谈斜率优化——截距优化

最近(两个月前)学习了斜率优化 —— 一种优化 1D1D 动态规划转移方程的高效方法,在较高难度的比赛中是一种十分常见的 DP 优化手段。鉴于我之前(一年前)也稍微接触过一点相关方面的知识,但是完全没有搞懂(太菜了),最近(两个月前)再配合 orzCJK学长 提出的截距优化的思想理念才对于斜率优化问题有了深刻的见解,故在这里对 orzCJK学长 的 斜率优化_截距优化!.pdf 进行详细的解释说明。

 

首先,1D1D 指的是状态数 O(n) 转移 O(n) 的动态规划方程。在满足一些条件的情况下,斜率优化可以将转移的 O(n) 优化至 O(logn) 甚至可以到 O(1) 。这样时间复杂度就由 O(n^2) 变为 O(nlogn) 甚至是 O(n) ,可见斜率优化的高效性。

如果有一个 DP 方程的某个状态为 f_i ,如果能推导出类似于 f_i=c_i + \min\limits_{j<i \land \cdots}{\{a_j + w_i \cdot b_j\}} ,那么这个转移方程就可以使用斜率优化进行优化。

然而普通的转移方程并没有什么特殊的地方,使用经典的方法(我也不会)略显繁琐,所以现在我们要赋予它以几何意义。(时刻注意,这个转移方程的意义是对于一个 ij < i 范围内寻找 j 使 a_j + w_i \cdot b_j)最小。)

换一下变量名,设 y_j=a_j, k_i=-w_i, x_j=b_j ,那么这样需要最小化的式子就变为 \underbrace{a_j}_{y_j} – \underbrace{-w_i}_{k_i} \cdot \underbrace{b_j}_{x_j} 。这不就是截距 b = y – kx 吗?!!也就是说,要最小化的就是一条\left(x_j, y_j\right)斜率为 k_i 的直线的截距

换句话说,把所有对于当前 i 可转移的 j 都表示为二维平面上的一个点 p_j=\left(x_j, y_j\right) ,我们需要做的就是在所有这样的点中,找到一个点,使经过它且斜率为 k_i 的直线的截距最小!这也是为什么斜率优化就是截距优化的原因,它其实优化的是截距!

现在想象一条斜率固定的直线从下往上平移,当它第一次经过某个点 p_j 时,这时的截距肯定取到最小值。那么这个点 p_j 在什么地方呢?显然,它会在所有 p 组成的下凸壳上。

那么现在只要维护这个下凸壳,每次在上面找点使得截距最小,拿来更新 …