Codeforces 476D Dreamoon and Sets - 規律構造輸出互質四元組

題目大意

構造 n 組四元組，每組 4 個正整數。要求：

1. 組內任意兩數 gcd = k。
2. 所有 4n 個數互不相同。
3. 使最大數盡可能小。

輸出最小可能的最大數，及任一合法構造方案。

關鍵轉化：除以 k 後兩兩互質

設四元組為 k·a, k·b, k·c, k·d。條件 gcd(k·x, k·y) = k ⇔ gcd(x, y) = 1。
問題轉化為：構造 n 組互質四元組，所有數互不相同，最大數最小。

規律發現與構造

觀察最小互質四元組：

第 1 組: 1, 2, 3, 5
第 2 組: 7, 8, 9, 11  ( = 第1組 + 6 )
第 3 組: 13, 14, 15, 17 ( = 第2組 + 6 )
...
第 i 組: 基礎 + 6*(i-1)

驗證：{6t+1, 6t+2, 6t+3, 6t+5} 中任意兩數差值 ∈ {1,2,3,4}，均與 6 互質，故兩兩互質。且組間差值為 6 的倍數，組間也互質 (因基礎數 ≤5，+6 後不共享質因子)。

最大數 = k * (6*(n-1) + 5) = k*(6n - 1)。

完整代碼

#include 
using namespace std;
const long long MOD = 1e9+7; // 本題無需模，但模板保留

int main() {
    long long n, k;
    while (cin >> n >> k) {
        long long max_val = k * (6*n - 1);
        cout << max_val << '\n';
        for (long long i = 0; i < n; ++i) {
            long long base = 6*i;
            cout << k*(base+1) << ' ' << k*(base+2) << ' ' << k*(base+3) << ' ' << k*(base+5) << '\n';
        }
    }
    return 0;
}

複雜度

• 時間：O(n) 輸出。
• 空間：O(1)。

證明最優性 (略)

每組需 4 個互質數，最小可用數為 1,2,3,5 (4 不能用因與 2 不互質)。每組佔用至少 4 個數，且模 6 看必須避開 0,4 (與 2,3 不互質)。每 6 個數最多取 4 個 (1,2,3,5)，故 n 組至少需 6n-1 範圍。構造達到下界，最優。