杂题集三
同余方程往互质方向考虑¶
I.六元组计数 - The 2024 Shanghai Collegiate Programming Contest - Codeforces
从问题终点反推，发现变量基本都是独立的，只需要求 \(a^{p}\bmod P\) 的信息，然后 NTT 合并一下。
从问题起点出发，可以通过原根的幂次来遍历 \(1,2,\cdots, P-1\)，把问题转化为
核心问题
对于 \(0\le i<M, 0<j\le N\)，然后对于所有 \(0\le t<M\)，求有多少组 \((i,j)\) 满足 \(i\cdot j \equiv t \pmod M\)。
其中 \(M\) 未必是素数，实际上是 \(P-1\)。
实际上这里适合 倒着 并 先假设互质性去想。
此外的操作都是很常规的解同余方程的手法：
- 先出一个有解的必要条件，一般是和模数作 gcd，无解直接排除；
- 然后可以同时约去 g，转化为一个充要条件，然后发现多了一个互质性，可以弄逆元操作。
解答
如果 \(t\) 和 \(M\) 互质，可以想到，\(j\) 如果不与 \(M\) 互质，那 \(i\) 就无解；反之，可以直接知道 \([0,M)\) 中间存在唯一解 \(i\)。
再尝试一般化。\(j\) 如果不与 \(M\) 互质则无解，实际上是利用了 \(\bmod M\) 后，与 \(M\) 的 \(\gcd\) 不变。也就是说有这样一个必要条件
所以有这样一个必要条件 \(g_1:=\gcd(j, M) | \gcd(t, M) =:g_1\cdot g'\)。 当这两个数字确定好了，我们前面的经验里直接算出了 \([0,M)\) 这样特殊的一组剩余系中有多少解，这里也试试。 $$ i \cdot g_1 \cdot \frac{j}{g_1} \equiv g_1\cdot g' \mod g_1\cdot M' $$ 希望把 \(g_1\) 约掉以求 \(\frac{j}{g_1}\) which is a integer 是一个与模数互质的数 $$ i \cdot \frac{j}{g_1} \equiv g' \mod M' $$ 于是 \(i\) 在 \(\bmod M'\) 意义下的结果又是唯一的，从而在 \([0,M)\) 这样特殊的一组剩余系中有 \(\frac{M}{M'} = g_1\) 个。
必要条件中这个整除性也给算法设计提供了遍历。
枚举复杂度就是经典的调和级数。
初始只有一个点引起的奇偶性不变量¶
想一下
00 -> 11
01 -> 10
11 -> 00
奇偶性保持不变。
这题面我最开始看错了，以为是一个正方体区域，于是知道 x 轴能确定后，y 自然确定，两个坐标唯一确定一个点。（于是造出了一个思路没有本质区别的新题）
实际上这题形状是 N 型。所以 y 轴并没有这样的不变量。但如果想象一个新坐标轴 \((x,x+y)\)，其实这个新 y 轴就有这样的不变量，回来找原 y 轴也是容易的。