分类： 数学

前言

难以置信, 遇到这个问题竟然是因为做一道CTF Reverse的题, 实际上我以前打ACM的时候都没有写过任意模数的K次剩余这种东西. 最简单的模质数的K次剩余的例题是
“`HDU 3930 Broot“`, 进阶版本(模任意奇数的K次剩余)的例题是“`BZOJ 2219 数论之神“`, 而终极版本(任意模数的K次剩余)似乎可以交的题只有“`51nod 1123“`, 截至本文写作时只有44个AC. 然而这个CTF题本身就有50多个通过了. ~~CTF>ACM 实锤~~ (暴论)

其实是因为这个Reverse的题里面幂指数是质数，所以会跟模数互质，然后就可以用RSA的方法来做了. 其次该题目更多的工作在于去花指令混淆上, 而非算法破解.

OK那么就来看一下这个问题从最简单的版本到终极版本怎么求解吧…

模质数的K次剩余

已知$a$, $b$, $p$, 求使得

$$
x^{a} \equiv b \quad(\bmod \ p)
$$

成立的所有 $x$. 其中 $p$ 是质数.

由于 $p$ 是质数, 所以 $p$ 存在原根 $g$ , 此时对于模 $p$ 意义下的任意数 $w$ ($0\le w \le p-1$) 存在唯一的 $i$ ($0\le i \le p-1$) 使得 $w\equiv g^i\quad(\bmod \ p)$.

由此可以将最终的答案用 $g$ 来表示: $x=g^{c}$, 带入上式转化为求解

$$
(g^{c})^{a}\equiv (g^{a})^c\equiv b \quad(\bmod \ p)
$$

此时 $g$, $a$, $b$, $p$, 已知, 只需要解出来 $c$. 此时相当于求解离散对数, 使用 Baby-Step-Giant-Step 可以在 $\mathcal{O}(\sqrt{p})$ 时间内得到一个特解 $x_0 \equiv g^{c} \quad(\bmod \ p)$.

在已知一个特解的情况下求出所有解是简单的, 由原根的性质可知 $g^{\varphi(p)}\equiv 1 \quad(\bmod \ p)$, 因此:

$$
\forall t \in \mathbb{Z}, x^{a} \equiv g^{c \cdot a+t \cdot \varphi(p)} \equiv b \quad(\bmod \ p)
$$

因此所有的解为:

$$
\forall t \in \mathbb{Z}, a \mid t \cdot \varphi(p), x \equiv g^{c+\frac{t \cdot \varphi(p)}{a}} \quad(\bmod p)
$$

上面幂次部分要能整除必须要有$\frac{a}{\operatorname{gcd}(a, \varphi(p))} \mid t$, 可以设 $t=\frac{a}{\operatorname{gcd}(a, \varphi(p))} \cdot i$, 于是得到所有的解为:

$$
\forall i \in \mathbb{Z}, x \equiv g^{c+\frac{\varphi(p)}{\operatorname{gcd}(a, \varphi(p))} \cdot i} \quad(\bmod p)
$$

HDU 3930 Broot 代码:

继续阅读“任意模数的K次剩余 /HDU 3930 Broot/BZOJ 2219 数论之神/51nod 1123 X^A mod B”

题目链接

题意：

给定一个长度为 $n$ 的序列 $a$ ，$n \le 10^6$ ，每个数字 $a_i$ ，满足 $0 \le a_i \le 10^6$ .

可以对这个序列进行一种操作，把第 $i$ 个数字中的一份移动到 $i-1$ 或者 $i+1$ .即操作过后 $i$ 处变为 $a_i-1 , a_{i+1}$ 或者 $a_{i-1}$变为 原来的数字+1.

问最少需要多少次操作使得存在某个数字 $k>1$ 满足所有的 $a_i$ 都可以被k整除（$0$可以被任何数整除），操作过程要满足所有的 $0\le a_i$ 。

题解：

考虑操作完成之后的结果，如果每一个数字都能被 $k$ 整除，那么显然 $S = \sum_{i=1}^{n} a_i$ 也可以被k整除。所以 $k$ 一定是 $S$ 的一个因数。

然后显然 $k$ 为合数时的情况，要么被 $k=其质因子$ 的情况包括，要么就劣于这种情况。所以我们只需要考虑 $k$ 为质数的情况，也就是 $S$ 的所有质因子。

由 $S$ 最大为 $10^{12}$ 可知，其质因子最多应该只有$10-20$种，而且分解出质因子可以用时间复杂度 $O(\sqrt{n})$ 的算法，也就是约 $10^6$ 。

继续阅读“[思维][贪心][贡献拆分] codeforces 1255 E2 Send Boxes to Alice (Hard Version)”

题目链接

题意：

求 $$\sum_{k=1}^{N}((kM)\& M)mod(10^9+7)$$

其中 $1 \le N \le 10^{18}$ , $1 \le M \le 10^{11}$

题解：

按位来做，考虑每一个二进制位i, 假设pi是 M 中从小到大第i位上的0/1), 然后我们又可以用取模和取整来取代某一位上的运算，比如当前处理的是第i位 ，就可以写成 $$\sum_{k=1}^{N}(\lfloor \frac{k*M}{2^i} \rfloor)-2*\sum_{k=1}^{N}(\lfloor \frac{k*M}{2^{i+1}} \rfloor)$$
这显然是一个类欧几里得的模板式子，我们只需要套用一下模板即可。最后把所有位的答案累加起来即可。
继续阅读“[类欧几里得][位运算] 2019牛客暑期多校训练营（第九场）I KM and M”

题目链接

题意：

$n$ 个集合，每个集合最多32个unsigned int范围的整数， $m$ 个询问，每次问下标在 $[l,r]$ 之间的集合能否表示出 $x$ 。数据范围 $1\le n,m\le 50000$，每个数字都在 unsigned int 以内。

题解：

线段树维护线性基即可。学习了一发板子。
继续阅读“[线性基][线段树][模板] 牛客多校第四场 B xor”