## EP2 ### 1.练习日Aranda给Z出的问题「数字比较」 待更新 ### 2.最大平局问题 X 给 Avantoge 的贪心法练习题，镜头有拍到 > 有 $n$ 个人站成一排玩石头剪刀布，每个人只会出一种固定的手势。定义一次操作为： > - 选择任意的相邻两人，让他们玩石头剪刀布，将败者移除。若平局，则任意…

在文章《题解：P14255 列车（train）》发表评论：

"对于一个固定的有端点" 有错别字，审核偷懒了（）

### 问题 设 $h_n$ 表示用以下方法将凸多边形区域分成三角形区域的方法数：在有 $n+1$ 条边的凸多边形区域内，通过插入在其中不相交的对角线而把它分成三角形区域。定义 $h_1=1$。求 $h_n$ 的通项形式？ ### 解法 #### Step 1：寻找递推关系 我们有 $h_2=1$，因为三角形不可以再分…

求 $$\lim_{n\rightarrow\infin}\left( \frac{\sqrt{1\cdot 2}}{n^2+1}+\frac{\sqrt{2\cdot 3}}{n^2+2}+\cdots+\frac{\sqrt{n(n+1)}}{n^2+n} \right)$$ - A.$1$ - B.$-1$ -…

求以下关于 $x$ 的方程的正整数解。 $x^{13}=21982145917308330487013369$ 有人直接注意到了 $x=89$，请允许我揭秘他的注意过程。 首先由于 $x^{13}$ 的末两位是 $69$，这意味着 $x$ 末位数字不是 $2$，也不是 $5$，那么 $x$ 就与 $10$ 互素，即 $…

设歌剧院内有 $n$ 座雕像，则雕像的编号依次为 $1\sim n$，假设雕像体积在一定范围内均匀随机。目前他们制定的策略为： 1. 从前 $r$ 个雕像中找出体积最大的雕像，设其体积为 $\max$。（第三个弟子的策略改进版即取 $r=\frac{n}{3}$） 2. 从后 $r+1\sim n$ 个雕像中选出第一个…

在讨论《正确性证明》回复：

@[潘德理2010](luogu://user/572133) 太妙了Orz

## Miller-Rabin ### 两个引理 #### 引理 $1$：费马小定理 设 $p\in\text{Prime}$，$a\in\mathbb{Z}$，且 $\gcd(a,p)=1$，那么有 $$a^{p-1}\equiv 1\pmod p$$ **证明：** 对于两个整数 $a\ne b\pmod p$，和…

在文章《题解：P3810 【模板】三维偏序（陌上花开）》发表评论：

为什么排序的时候是对开区间排序 没看懂qwq

## KMP KMP算法可以在 $\mathcal{O}(n+m)$ 的时间复杂度内完成串的匹配。 其核心思想在于 $nxt$ 数组（也叫 $border/fail$）。$nxt[i]$ 的意义是：前缀 $[1,i]$ 最长相同的真前缀和真后缀的长度。 例如 ```abcabb```，$nxt[5]$ 的值为 $2$（…

在讨论《莫队卡常》回复：

@[wQWQw](luogu://user/490704) 那么牛？%%%

在讨论《莫队卡常》回复：

莫队被卡了qwq拼尽全力只能50pts @[lxy512](luogu://user/1401585)

在讨论《【07.23】数学趣题》回复：

发这了： 原式太大了，不妨两边同时取对数 $$\ln n!>q\ln p$$ 考虑斯特林近似 $$n!\approx\sqrt{2\pi n}(\frac{n}{e})^n$$ 那么 $$\ln n!\approx n \ln(\frac{n}{e})+\frac{1}{2}\ln 2\pi n=n(\ln n-1)+…

在讨论《【07.23】数学趣题》回复：

@[cx2021hjxhjx](luogu://user/1277550) 云剪贴板炸了吗？

在讨论《【07.23】数学趣题》回复：

@[c_legg](luogu://user/1054383) 写错了，函数 $f(x)=\ln x!-q\ln p$ 不方便直接对 $\ln x!$ 求导，所以先用斯特林近似将其转化为简单代数运算，才能求导

在讨论《【07.23】数学趣题》回复：

@[aleph_](luogu://user/552255) 忘记补充了，强制在线，不可以乱搞❌

在讨论《【07.23】数学趣题》回复：

@[c_legg](luogu://user/1054383) [此处为答案](https://www.luogu.com.cn/paste/baxojt56) 其他看到本题的人请先思考再点击查看。

在讨论《【07.23】数学趣题》回复：

@[c_legg](luogu://user/1054383) $10^9$ 级别的指数估算位数误差挺大的，不太行哦

$t$ 次询问，每次给出两个正整数数 $p,q$，求最小的正整数 $x$，使得 $x!>p^q$. $t\le 7\times 10^6$，$p,q\le10^9$.

如果你60pts： - 不可用费马小定理求逆元，因为 $b$ 不一定是质数。 - 如果用 exgcd 求逆元，需要注意本题要求 $n\in \N$，解出的逆元需要变成非负的。 具体操作只需 ```x=(x%b[i]+b[i])%b[i]``` 即可。 - 此外还需注意 $a$ 可能是负的，要提前变正。 同样地，```a…

已知正实数 $a,b$ 满足对任意实数 $x$ 均有 $a \cos2x - b \cos x \ge -2$，则 $2a+b$ 的最大值为？ 最近在练莫反相关的内容，顺便推荐一下几道题： - [P1829](https://www.luogu.com.cn/problem/P1829) （经典题，涉及到很多经典处理技…

### 狄利克雷卷积： $$h(n)=\sum_{d|n}f(d)g(\frac{n}{d})$$ 记作 $h=f*g$ 另一种形式：$h(n)=\sum_{xy=n}f(x)g(y)$，是一样的。 #### 性质： - 满足交换律（易得，因为 $d$ 和 $\frac{n}{d}$ 地位相同） - 满足结合律（$(f…

在讨论《【07.20】今日份数学题》回复：

@[Sunrise_beforeglow](luogu://user/812227) 妙啊。

在讨论《捞》回复：

@[alpharchmage](luogu://user/411141) 这年头国内看无机的已经不多了。

在讨论《【07.20】今日份数学题》回复：

@[I_Love_DS](luogu://user/1118614) 楼主太菜了不会html，看你id很会玩DS哦，能否用DS帮我生成一个（doge）

在讨论《【07.20】今日份数学题》回复：

我的方法： 从下列恒等式开始： $$(1+x)^n=\sum_{k=0}^n\binom{n}{k}x^k$$ 两边关于 $x$ 求导，得到 $$n(1+x)^{n-1}=\sum_{k=1}^n k\binom{n}{k}x^{k-1}$$ (1) 将 $x=1$ 代入 (1) 式，得 $$n2^{n-1}=\sum…

在讨论《【07.20】今日份数学题》回复：

@[Phartial](luogu://user/376161) 居然真有这个序列！？OEIS还是太权威了。

在讨论《【07.20】今日份数学题》回复：

@[Sunrise_beforeglow](luogu://user/812227) 咦你这个方法十分巧妙！能不能一直用相同方法拆，得出第三问？

【Medium+】 证明下列恒等式成立： (a) $\sum_{k=1}^n k\binom{n}{k}=n2^{n-1}$ (b) $\sum_{k=1}^n k^2\binom{n}{k}=n(n+1)2^{n-2}$ (c) 求下列式子相对于任意正整数 $p$ 的恒等式： $$\sum_{k=1}^n k^p\b…

在讨论《如何优雅地证明》回复：

@[da_ke](luogu://user/766675) 学到了 还可以用Lagrange求/强