2023.10.03T2
Solution
在 \(\bmod{2}\) 意义下，\(-x^{c} = x^{c}\)。
对于 \(A_i \equiv C \pmod{B}\)，变为 \(A_i - C \equiv 0 \pmod{B}\)，那么 \(-C\) 操作可以看成是 异或 上 \(C\)。
对于 \(A^{'}_i \equiv 0 \pmod{B}\) 的形式，欲找到最大的 \(B\)，则 \(B\) 显然是 \(\gcd\limits_{i = 1}^{n}(A^{'}_i)\)。
利用辗转相除法的思想求多项式的 \(\gcd\)。
对于 \(\gcd(a, b)(a > b)\)，将其转为 \(\gcd(a - xb, b)\)，其中 \(x\) 的作用是把 \(b\) 的最高位与 \(a\) 的最高位对齐，这样每次可以将 \(a, b\) 中较大的二进制数位减少 \(1\)。
做单次 \(\gcd\) 是 \(O(n^2)\) 的，总时间复杂度为 \(O(n^3)\)。由于是二进制操作，考虑用 bitset 优化成 \(O(\frac{n^3}{w})\)。
2023.10.03T3
Solution
考虑对于 \(\{ 0, 1, 2, \dots, 2^{n} - 1 \}\) 进行操作。
拆位进行考虑，发现对于一个数 \(x\)，进行 \(m\) 轮操作后，它将变为 \(x^{'}\) 满足：
- \(x^{'}\) 的高 \(n - m + 1\) 位是 \(x\) 的低 \(n - m + 1\) 位。
- \(x^{'}\) 的低 \(m\) 位是 \(x\) 的高 \(m\) 位翻转后的结果。
至于这个结论是怎么猜的，可以结合 FFT 的实现原理。
于是对于每组询问的 \(x\)，我们可以得到 \(m\) 次操作后对应的 \(x^{'}\)。这本质上是 二进制下各数位的置换！
于是对 \(n + 1\) 个二进制位做 \(O(n)\) 置换快速幂即可。
时间复杂度 \(O(nQ)\)。
标签：03,gcd,pmod,2023.10,二进制,补题,equiv From： https://www.cnblogs.com/Schucking-Sattin/p/17741446.html