Loading...
NOI2021 加油！
题意：求$a^x \equiv b(\mod p^e)$ 的最小整数解。 $3 < p \leq 50,p^e \leq 10^18,a\nmid p,b \nmid p$，询问不超过 $1000$ 组。暴力分跑 bsgs 其实就可以了...因为保证了 $(a,p^e) = 1$。 但是这样显然会 T，于是我们就不要往 bsgs 的方面去想了。 我们考虑 $p$ 很小并且 $>2$，这...
记录各种我这种数论菜鸡不会的式子。。。可能有很 zz 的式子大佬不要嘲笑<h3>整除与不定方程</h3> $d|a,d|b \Leftrightarrow d|(a-b)$ 证明：$a = pd,b = qd,a-b = (p-q)d$$(a,b)|d \Leftrightarrow ax+by = d$ 存在整数解。证明：从右往左推：令 $g=(a,b)$,则有 $...
题目描述：给你若干条形如 $x+y=c$ 或 $x-y=c$ 的直线，这些直线与坐标轴的夹角是 45 度，问在矩形 $(0,0) \to (W,H)$ 中，有多少个子矩形。图片示意：上图有 $19$ 个子矩形。$n \leq 10^5$首先这一题目 $O(n^3)$ 的复杂度十分好做：就是枚举三条边 去 map 找一下第四条边就好了。我们考虑如何做到 $O(n^2logn)$:我们可以考虑先...
请输入密码访问
DDP（动态 dp），是通过将状态改写成矩阵，然后定义具有结合律的与转移等价的运算，用数据结构快速维护的一种方法。在 NOIP2018 时作为 Day2 T3 出现。 NOIP2018 Day2T3 - 保卫王国 考场上根本不会...那个时候我是连暴力 dp 都不会的菜鸡，现在回来学一学。 我们来找一道简单的题目入手：给定一棵树，点有点权，每次可以修改一个点的权值，每次修改后求这棵树的最大独...