我们设Sij表示左上角是Aij的子矩阵的和。

那么有两个重要的性质：

1. Sij + N × M = Si+1,j+1
2. 当y>=N时，S1,y=S1,y+1。当x>=M时，Sx,1=Sx+1,1。

根据性质1，我们只要知道S11的值，那么S11,S22,S33...这条对角线上的子矩阵和哪些是K的倍数，只要解一个同余方程S11+xNM=0 mod K。这个方程可以先用O(K)的预处理求出xNM=0 ... K- 1 mod K的解，每次求S11+xNM=0 mod K的解是查表即可。另外也可以用扩展欧几里得的方法直接求解。

同理知道S12可以得到S23,S34,S45...

根据性质2，我们只要求S11,S12,S13...S1N和S21,S31,S41...SM1这O(N+M)条对角线上哪些子矩阵是K的倍数就行。

最后每个子矩阵求和可以O(1)得出（找规律用数学方法求和）。

总的时间复杂度是O(N+M)。