我们设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的倍数可以O(1)求出。只要解一个同余方程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)。