Codeforces 509D Restoring Numbers：構造與數學（GCD 應用）

題目大意

給定 n×m 矩陣 w，判斷是否存在正整數 k 和非負整數數組 a[1..n]、b[1..m]，使得：
w[i][j] = (a[i] + b[j]) % k，且 0 ≤ w[i][j] < k。若存在輸出任意一組解，否則輸出 NO。

核心數學推導

必要條件

對任意 i1,i2,j1,j2，由模運算性質可得：
(w[i1][j1] + w[i2][j2]) % k = (w[i1][j2] + w[i2][j1]) % k
即 k 必須整除 D = w[i1][j1] + w[i2][j2] - w[i1][j2] - w[i2][j1]。

構造 k

計算所有 2×2 子矩陣的 D 的絕對值，取其 GCD 為 g。若 g == 0，說明矩陣滿足加法結構，可任取 k > max(w)（如 1e9+7）。否則 k = g，但需驗證 k > max(w)，否則無解。

構造 a、b

固定 a[1] = 0，則 b[j] = w[1][j]。
對 i > 1，a[i] = (w[i][1] - b[1] + k) % k。
最後驗證所有 (a[i] + b[j]) % k == w[i][j]。

完整代碼

import java.util.*;
public class CF509D {
    int n, m;
    long[][] w;
    long[] a, b;
    long gcd(long a, long b) { return b == 0 ? a : gcd(b, a % b); }
    public static void main(String[] args) { new CF509D().run(); }
    void run() {
        Scanner in = new Scanner(System.in);
        n = in.nextInt(); m = in.nextInt();
        w = new long[n][m];
        a = new long[n]; b = new long[m];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                w[i][j] = in.nextLong();
        long g = 0;
        for (int i1 = 0; i1 < n; i1++)
            for (int i2 = i1+1; i2 < n; i2++)
                for (int j1 = 0; j1 < m; j1++)
                    for (int j2 = j1+1; j2 < m; j2++) {
                        long d = Math.abs(w[i1][j1] + w[i2][j2] - w[i1][j2] - w[i2][j1]);
                        g = gcd(g, d);
                    }
        if (g == 0) g = 1000000007LL; // 任意大於 max(w) 的數
        else if (g <= maxElement(w)) { System.out.println("NO"); return; }
        a[0] = 0;
        for (int j = 0; j < m; j++) b[j] = w[0][j];
        for (int i = 1; i < n; i++)
            a[i] = (w[i][0] - b[0] + g) % g;
        boolean ok = true;
        for (int i = 0; i < n && ok; i++)
            for (int j = 0; j < m; j++)
                if ((a[i] + b[j]) % g != w[i][j]) { ok = false; break; }
        if (!ok) { System.out.println("NO"); return; }
        System.out.println("YES");
        System.out.println(g);
        for (int i = 0; i < n; i++) System.out.print(a[i] + (i==n-1?"\n":" "));
        for (int j = 0; j < m; j++) System.out.print(b[j] + (j==m-1?"\n":" "));
    }
    long maxElement(long[][] w) {
        long mx = 0;
        for (long[] row : w) for (long v : row) if (v > mx) mx = v;
        return mx;
    }
}

關鍵點總結

• 利用模運算線性性質推導 k 的必要條件（GCD）。
• 構造解時固定一個變量（如 a[1]=0）消除自由度。
• 邊界情況：g=0 時矩陣已滿足加法結構，k 可任取大數。