等待修复中,暂未开放,或者需要输入神秘代码:
CTF Web 原创题三道
Win32 下 Hook 函数的几种方法
OpenWrt 打通 IPv6 校园网
Legacy Toolset(纪念用)
Wireguard Network, Chaining and Routing
栈溢出 —— 初级 ROP 学习记录
菜鸡首发 CTF || 部分 WriteUp & 学习经验
[研学] 质因数分解及素性判定
[研学] 质因数分解及素性判定
时间:2018.10 ~ 2019.3
参加成员:Modem_ Lagoon _Qijia mnihyc
感觉这个是人生巅峰了, Lagoon 上清华,剩下我们三也退役了,摆在这留作纪念ww 拿濑户口的话来说,就是萌新那会才是最辉煌的时期www
-
【序言】
质数的研究一直是数学与信息学领域中的重要课题,质数的判定与质因数分解在现代通讯保密领域中更是发挥着重要的作用,本课题小组将通过此次研学机会对不同规模下自然数素性判定及质因数分解的有效算法进行探究,加深对该领域的了解和理解。
-
【1.0】素数的定义
素数,又称质数。一个数 \(n\) 是素数当且仅当它是大于 \(1\) 的自然数且它的因数有且仅有 \(1\) 与 \(n\) 。
-
【1.1】记号与规定
-
- 记 \(\displaystyle\mathbb{R}\) 表示实数集,\(\displaystyle\mathbb{N}\) 表示自然数集,\(P\) 表示素数集。
- 勒让德符号 \(\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)\) 。