【模板】动态 DP & 动态树分治 题解
「NOIP2018」保卫王国 题解
「SCOI2015」小凸玩密室 题解
Task Supercomputer 题解
「SDOI2017」数字表格 题解
题目大意
求 \[\prod \limits_{i = 1}^{n} \prod \limits_{i = 1}^{m} f_{\gcd(i, j)}\] 其中 \(f_i\) 为斐波那契数列。
Miller Rabin 与 Pollar-Rho
Miller Rabin 质数判定
费马小定理
众所周知
当 \(p\) 是质数， 对于任意 \(a\)，有 \[a^{p - 1} \equiv 1 \pmod{p}\]
二次剩余
当 \(p\) 是质数，对于 \(x \in (0, p)\)，关于 \(x\) 的方程 \(x^2 \equiv 1 \pmod{p}\) 的解为 \(x = 1 \ or \ p\)。
两个逆定理同样成立。
下面开始正题
对于任意 \(a\)，令 \(p - 1 = 2^qm, m = 2n + 1, n \in \mathbb{N}\)： - 根据费马小定理，如果 \(a^{p - 1} \not\equiv 1 \pmod{p}\)，那么 \(p\) 不是质数； - 根据二次剩余，如果 \(a^{p} \equiv 1 \pmod{p}\) 但 \(a^{p - 1} \equiv 1 \pmod{p}\)，那 \(p\) 不是质数。
那么我们不断选择 \(a\) 进行检验。
如果 \(p\) 是质数，那么通过以上两个测试的概率为 \(1\)；如果 \(p\) 不是质数，那么通过以上两个测试的概率为 \(\frac{1}{4}\)。
只要取足够多个 \(a\)，那么就能将错误率降低到可以接受的范围内。
如果是 int 范围那么 \(10\) 次左右可以保证正确，如果是 long long 那么 \(20\) 次。
或者还有一种方法直接令 \(a\) 为前 \(10 \sim 20\) 个质数，至少 long long 范围内没有什么问题。
共价大爷游长沙
先膜毛爷爷。
题目描述
给出一棵动态的树，有一个集合 \(S\)，每次询问集合中的所有点相连的路径是否一定经过 \((x, y)\)。
四种操作： - \(\text{opt} = 1, x, y, u, v\)：删除边 \((x, y)\)，增加边 \((u, v)\)； - \(\text{opt} = 2, x, y\)：在集合 \(S\) 中加入 \((x, y)\)； - \(\text{opt} = 3, x\)：删除第 \(x\) 个加入集合 \(S\) 的点对； - \(\text{opt} = 4, x, y\)：询问集合中的所有点相连的路径是否一定经过 \((x, y)\)。