题目链接题目大意有两个长度为 $n$ 的序列序列 $a$ 和 $b$，要求你计算出一个长度为 $n$ 的序列满足我们令 $sm_d = \sum_{d|j} [b_j \geq b']$。发现 $sm$ 只会根据 $b'$ 的变化而变化 于是我们想到了整体二分。整体二分的时候运用类似于莫队的移动指针的技巧 预处理因数分解和 $\mu$ 就可以快速判定了。时间复杂度 $O(nlog^3n)$...
题意：给你一个序列s，你把这个序列的所有不同排列按字典序排列后，求s的排名mod m 不保证 $m$ 是质数。 题解：我们记 $cnt_i$ 表示填到当前 $i$ 这个数还有多少个，不难发现题目要求的是： 显然后面的和式可以用树状数组轻松维护。 发现 $m$ 不一定是个质数，我们质因数分解后对于每一个 $p_i^{e_i}$ 分开做就好了。中间要将所有的数的 $p_i$ 因子都提取出来。（感...
题目链接 首先 $f_{[1\cdots k-1]} = 1$，所以发现每个 $f_x$ 都可以表示成 $f_k^e$ 的形式。 我们首先通过矩阵乘法算出来 $f_k^e = f_n$ 的解，然后就是解方程 然后因为 $g = 3$，用 BSGS 算出两项，最后用 exgcd 解出 $e$ 直接代入即可。 代码:/* * Author: RainAir * Time: 2019-07-...
题意：求$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 的式子大佬不要嘲笑整除与不定方程 $d|a,d|b \Leftrightarrow d|(a-b)$ 证明：$a = pd,b = qd,a-b = (p-q)d$ 2. $(a,b)|d \Leftrightarrow ax+by = d$ 存在整数解。证明： 从右往左推：令 $g=(a,b)$,则有 $g|ua,g|vb \Right...