Codeforces 1477A - Nezzar and Board (設計解題、暴力搜尋 Brute force)

題目大意：

有一個黑板上有許多數字，你可以透過 \(z = 2x-y\)，其中 x,y 為黑板上的數字且可以相同，你可以將 z 在寫到黑板上，並且 x,y 不移除，試問能否用黑板的數字求出 k？

題目連結

重點觀念

• 能夠將 \(2x-y\) 進行推導與聯想
• 了解貝祖定理

分析：

好題，太好了，能寫出來的都是天才八。

我們將推導進行分解，方便理解。

Step A: \(2x-y = k\) 推導

• 我們可以將 \(2x-y = k\)，理解成 \(x-y=k-x\)。
• 再來我們進行分析，公式推導
  • \(x_i = x_j + (x_j - x_k) \)
  • \(x_a = x_i + (x_i - x_b) \)
  • \(x_c = x_a + (x_a - x_d) \)
  • 我們就可以將 \(x_c\) 表示為 \(x_c = x_j + (x_j - x_k) + (x_i - x_b) + (x_a - x_d) \)
  • 因此我們公式就成了 \(\sigma (x_i - y_i) = k - x_i\)，sigma 不用白板數字全部累加，只要我們需要的就好，我們也可以針對需要的不斷進行操作，也就是可以 \(y(x_i - y_i) = k - x_i\)。
• 再來我們可以透過 \(2x-y = k\) 反覆求得 x or y。
  • \(2x-y = k = x + (x-y)\)，這裡我們把 \(x + (x-y) \) 視為新的數字(k)
  • 將 k 視為 \(x + (x-y) \) 跟原先的 x 在嘗試一次 \(2x-y\)
    就可以理解成為 \(2x - [x + (x-y)] = 2x - 2x + y = y\)，可以透過此推導再次求回 y，反之，也可以求出 x，將係數相反放即可。
• 因為可以透過 \(2x-y\) 不斷求出 x 與 y，因此我們可以理解此數學式 \(\sigma (x_i - y_i) = k - x_i\) 為 \(\sigma (x_i - x_1) = k - x_1\)，其實 \(x_1\) 為隨便一個 x 數值即可，因為每個 x 都可以被 \(2x-y\) 反覆求出。
• 再來我們將這個公式寫成方程式，\(y_1(x_1-x_1) + y_2(x_2-x_1) + y_3(x_3-x_1) + … + y_n(x_n-x_1) = k - x_1 \)，其中 y 值可以為 0 or 1，不斷產生的 \(x_i\)，如果我們求出的 k 不會用到就可以讓 y 為零。

Step B: 貝祖定理

貝祖定理是關於最大公因數的其中一個定理之一，此定理說明 \(ax+by = dm\)，其中 a,b 為已知數值，m 為 a,b 最大公因數，d 為倍率。

詳細證明請參考貝祖定理 - wiki

因此就可以讓貝祖定理套用在 \(y_1(x_1-x_1) + y_2(x_2-x_1) + y_3(x_3-x_1) + … + y_n(x_n-x_1) = k - x_1 \) 此公式，只要證明 \(k - x_1 = gcd( \sigma(x_i- x_1))\) 即可。

Step C: 可是 \(y_1(x_1-x_1) + y_2(x_2-x_1) + y_3(x_3-x_1) + … + y_n(x_n-x_1) = k - x_1 \) 此公式只有用到已知的 x，那我們根據 \(2x-y\) 所推出來的數值不就都沒有用到嗎?

這裡就又一個新推導了，我們假設白板上只有兩個數字 a,b，我們可以給他進行反覆操作

• \(2a-b\) 是新的數值
• \(2b - 2a-b = b - 2a\) 又是新的數值
• \(2(2a-b) - b = 4a - b \)，這裡我們假設 \(4a -b = k\)
• 因此 \(k = 4a - 1b\)，這裡會符合貝祖定理，因此 \( k = gcd(a,b) \)

因此我們可以推論出只要是透過原先白板的數值推出的值都一定會符合 \(gcd(a,b)\)。

Step D: 求出公式

只要 \(\gcd(x_i - x_1) = d(k - x_i) \) 就可以被解出，也就是只要 \(\gcd(x_i - x_1) \ mod \ (k - x_i) = 0 \)，就是有解。

d 則是貝祖定理的數值，並不再本題討論中，詳請須看貝祖定理的證明

參考來源

• Codeforces Round #698 (Div. 2) D. Nezzar and Board（一步步推出来，超级清晰，不猜结论，看不懂来打我 ~ 好题 ） - 繁凡さん
• Editorial of Codeforces Round #698 (Div.1, Div.2) - Nezzar’s blog
• 貝祖定理 - wiki

心得

這題真的是一個好題，複雜的推導，又需要用到數學定理，現在回頭想想或許 \(2x-y=k\)，題目這裡其實就在暗示這題可以使用貝祖定理來解，但因為寫題目的經驗不夠多沒有反應到，錯失了寫出這題的能力，好可惜呀！

也要謝謝繁凡さん的 blog，他寫得很詳細，如果沒有他的 blog，我可能還沒有辦法意識到自己到底怎麼錯的，錯在哪，正確的思維要怎麼走。

題外話，我看懂這題花了 3hr，是不是有點太笨了QQ。

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define MAXN 1000200
#define int long long
#define LOCAL
using namespace std;
int t, n, k;
int num[MAXN];

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
#endif // LOCAL
    cin >> t;
    while(t--){
        cin >> n >> k;
        for(int i = 0; i < n; i++) cin >> num[i]; //輸入數列
        sort(num, num+n); //排序，以免會有相減，減出負值的冏境發生，讓 gcd 失靈。
        int x1 = num[0], gcd = 0; //c++ 的 gcd 在其中有一值為 0 時，gcd 為另一數
        //這裡不可以用 1，這樣最大的公因數永遠會是 1
        for(int i = 1; i < n; i++) gcd = __gcd(gcd,num[i] - x1); 
        //開始找所有數列的最大公因數
        if((k - x1) % gcd == 0) cout << "YES\n";
        //如果可以整除表示符合貝祖定理，證明可解。
        else cout << "NO\n";
    }

    return 0;
}

思考流程

透過紙筆與黑板而思考而成的片段，放在網路上供我紀念XD

錯誤的程式碼就不放上來讓大家見笑了QQQQ。