这是昨晚CF D的题解：

首先，我们来计算一下目前不同类型山峰之间的高度差，记作 $D$ 。

然后，对于每个大小为 $k \times k$ 的子矩阵，我们将计算不同类型山脉高度之和的差值是如何变化的。也就是说，对于每个子矩阵，我们将计算其中 0 和 1 的数量差异，让这些值为 $d_{i}$ ，然后会有 $q = (n - k + 1) \cdot (m - k + 1)$ 。这可以通过二维前缀和或 "滑动窗口 "来实现。

之后，我们可以正式写出下面的等式：

$$c_{1} \cdot d_{1} + c_{2} \cdot d_{2} + \dots + c_{q} \cdot d_{q} = D$$

其中 $c_{1}$ , $c_{2}$ , ..., $c_{q}$ - 是尼基塔为特定子矩阵选择的常数 $c$ （如果我们不使用该子矩阵变换，则为 $0$ ）。这与 Diophantine 方程非常相似，事实上也是如此，只不过有 $q$ 个未知数。

关于这个方程在整数中是否存在解？为此，只要

$$D \bmod gcd(d_{1}, d_{2}, \dots, d_{q}) = 0$$

值得一提的是，有必要仔细处理所有 $d_{i} = 0$ 的情况，同时也不要忘记 $D$ 最初等于 $0$ 的情况。

总之，解在 $O(n \cdot m + \log A)$ 中。

我就是不太明白，为什么

$$c_{1} \cdot d_{1} + c_{2} \cdot d_{2} + \dots + c_{q} \cdot d_{q} = D$$

只要

$$D \bmod gcd(d_{1}, d_{2}, \dots, d_{q}) = 0$$

就有解？

是什么定理吗？还是怎么推的？