CSUST - 2021 湖南省赛选拔赛

比赛链接 (ps: 写题请到Problems页面) 可能算详解?代码部分随缘写。 ...

September 15, 2021 · 6 min · Kenshin2438

吉老师线段树 - Segment tree Beats  [draft]

很抱歉的是,关于吉老师线段树历史最值问题本文尚并未涉及。 (开个新坑) 只是最近写题时觉得它让我对线段树的使用有了新的理解,故做记录。 ...

September 7, 2021 · 7 min · Kenshin2438

一类同余方程的解法 - BSGS  [draft]

Baby Step, Giant Step 解决这样一类同余方程的方法 $$a^x \equiv b\pmod c$$ 结合原根的知识还能解决模数有原根的$N$次剩余问题 $$x^n \equiv b\pmod c$$ ...

September 5, 2021 · 2 min · Kenshin2438

珂朵莉树 - Chtholly Tree

随机数据下十分优秀的处理区间赋值操作的暴力数据结构。 本篇只给出split和assgin操作的代码,其它更暴力的就不提了,一般的能用的情况下有这两个应该就够了。 ...

September 4, 2021 · 2 min · Kenshin2438

二次剩余 - Cipolla/Tonelli-Shanks

对于二次剩余式 $$x^2\equiv n\pmod p$$ 其中$p$为奇素数,且$p \nmid n$,求$x$。 ...

August 30, 2021 · 2 min · Kenshin2438

欧拉定理(数论) 及其拓展 - Extended Euler Theorem

$\forall a<m,(a, m)=1$,均有$a^{\varphi(m)}\equiv1\pmod{m}$,于是就有欧拉定理: $$a^n\equiv a^{n \mod \varphi(m)} \pmod{m}$$ 对于$n$取值较大的情况(比如$10^{30000}\mod 13$),欧拉降幂的作用不可忽视,但局限的是必须满足$(a,m)=1$才能有上式恒成立。 由于上述形式流传甚广,读者大抵早已熟记于心,这里便不再赘述。本文的最终目的是介绍另一个适用范围更广的版本,即所谓拓展欧拉定理。 $$a^n\equiv a^{n \mod \varphi(m) + \varphi(m)} \pmod{m} \quad \textrm{if }n \geq \varphi(m)$$ ...

August 28, 2021 · 3 min · Kenshin2438

莫比乌斯反演问题记录 - Mobius Inversion

题外话:好像文章有点长,本地调的时候加载目录都掉帧了。虽然一度想删点题目,但思前想后还是一题没删,总感觉每一题都代表了一种典型,实在不好取舍,或许只写推导会好一点,但还是有点怕代码的实现未有较好交代。。。 好了,闲言少叙。 本篇是平时刷的反演题目的解题记录,个人认为这方面的知识点和写题目是有点脱节的,题目要么是纯套路,要么就是有些不太友好的小技巧。 题目来源:Luogu, LibreOJ, HDU等。 ...

August 27, 2021 · 16 min · Kenshin2438

三角函数降幂公式 - Power-reduction formulae

先给出全部公式: $$\begin{aligned} & \sin^{2n}{x}=\frac{1}{2^{2n-1}}\left[ \sum_{k=0}^{n-1}{2n \choose k}(-1)^{n-k}\cos{2(n-k)x} + \frac{1}{2}{2n \choose n} \right] \\ & \sin^{2n+1}{x}=\frac{1}{2^{2n}}\sum_{k=0}^{n}{2n+1 \choose k}(-1)^{n-k}\sin{(2n-2k+1)x} \\ & \cos^{2n}{x}=\frac{1}{2^{2n-1}}\left[ \sum_{k=0}^{n-1}{2n \choose k}\cos{2(n-k)x}+\frac{1}{2}{2n \choose n} \right] \\ & \cos^{2n+1}{x}=\frac{1}{2^{2n}}\sum_{k=0}^{n}{2n+1 \choose k}\cos{(2n-2k+1)x} \\ \end{aligned}$$ ...

August 1, 2021 · 1 min · Kenshin2438

筛法 - Sieve  [draft]

info Update 2021.10.03 增加PN筛 包含有: 线性筛,杜教筛,Min25筛,PN筛 TODO: 州阁筛 本篇主要用于入门数论中的一些简单的筛法 虽然不是特别全面,但是后面会一步步完善的。 注意:不会对用到的数论函数解释,默认读者对数论有基本认知。 ...

July 28, 2021 · 13 min · Kenshin2438

孙子剩余定理 - CRT/exCRT  [draft]

之前介绍Lucas定理时,内容涉及到了中国剩余定理,以及欧拉定理。 后者应该是广为人知的定理(之后也会写拓展欧拉定理的吧),然而前者的名气似乎远有不如。 本篇以证明为主,(不喜欢证明的可以关了)当然也会遵循传统给出板子。 ...

July 25, 2021 · 2 min · Kenshin2438