数据比较强的 BSGS 题,很多细节都卡到了√ 题目描述 小 W 喜欢读书,尤其喜欢读《约翰克里斯朵夫》。最近小 W 准备读一本新书,这本书一共有 $P$ 页,页码范围为 $0 \cdots P-1$。 小 W 很忙,所以...
同余
BSGS/exBSGS 学习笔记【同余】
〇、前言 BSGS 是用来求形如 $a^x\equiv b\pmod p$ 的最小非负整数解的算法。 当 $\gcd(a,p)=1$ 时可以直接使用 BSGS,当 $\gcd(a,p)\ne 1$ 时需要用到 exBSGS 进行转化。 参考资料: PoPoQQQ 《原根与指标》...
洛谷 P2480 [SDOI2010]古代猪文 题解【CRT】【欧拉定理】【Lucas定理】
数论综合题。 题目背景 题目背景与题目无关因此省略。题目链接 题目描述 猪王国的文明源远流长,博大精深。 iPig 在大肥猪学校图书馆中查阅资料,得知远古时期猪文文字总个数为 $N$。当...
洛谷 P4774 / loj 2721 [NOI2018] 屠龙勇士 题解【同余】【exgcd】【exCRT】
推导过程存在漏洞+exCRT板子没打熟于是期望得分÷实际得分=∞? 题目描述 小 D 最近在网上发现了一款小游戏。游戏的规则如下: 游戏的目标是按照编号 $ 1\sim n$ 顺序杀掉 $ n$ 条巨龙,每条巨龙...
扩展中国剩余定理 exCRT 学习笔记
前言 由于 $ \{\mathrm{CRT}\}\subseteq\{\mathrm{exCRT}\}$,而且 CRT 又太抽象了,所以直接学 exCRT 了。 摘自 huyufeifei 博客 这么抽象的东西我怎么可能会写 前置技能 g...
洛谷 P3244 / loj 2115 [HNOI2015] 落忆枫音 题解【拓扑排序】【组合】【逆元】
组合计数的一道好题。什么非主流题目 题目背景 (背景冗长请到题目页面查看) 题目描述 不妨假设枫叶上有 $ n$ 个穴位,穴位的编号为 $ 1\sim n$。有若干条有向的脉络连接着这些穴位。穴位和...
洛谷 P2261 [CQOI2007]余数求和 题解【数学】【同余】
数学题(听说对学莫比乌斯反演有用? 题目描述 给出正整数 $ n$ 和 $ k$ 计算 $ G(n, k)=k\ \bmod\ 1 + k\ \bmod\ 2 + k\ \bmod\ 3 + \cdots + k\ \bmod\ n$ 的值 其中 $ k\ \bmod\ i$ 表示 $ ...
完全背包问题 题解【有后效性的DP】【最短路】【背包】【同余】
后效性处理+背包合法性转化…又是玄学操作,不过感觉对DP的理解又深入了一些。 题目描述 有\(n\)种物品,物品的体积分别为\(V_1,V_2,\dots,V_n\),且每种物品的数量都可以看做是无限多的...
欧几里得及扩展欧几里得算法【学习笔记】【数学】【同余】
负一、upd on 2019.3.20 学 CRT 的时候发现了求通解时候的一个小问题。改起来有点麻烦,于是顺便把 html 代码全改成了 md…… 〇、前言 以前扩展欧几里得推过几次,但是总是推不懂,理解起来非常费劲。快联赛了...
CF1070A Find a Number 题解【BFS搜索】【同余】【图论】
当时打这场ACM的时候是julao队友Mayfly做出来的,要把数位转化到图上去跑。 Description You are given two positive integers \(d\) and \(s\). Find minimal positive integer \(n\) which is ...