UVa11565 - Simple Equations (數論 Math theorm、暴力搜尋 Brute force)

題目大意

你必須找出 x,y,z 三個數字符合下面的公式，其中 x,y,z 數字不可以相同

• \(x+y+z = A\)
• \(xyz=B\)
• \(x^2 + y^2 + z^2 = C\)

給你 A,B,C 求出 x,y,z，如果有多組答案，請輸出依序最小的

題目連結

重點觀念

• 對於暴力搜尋進行優化
  • 反推 z
  • 了解題目數值最大上限
  • 得知題目可以負整數

分析

其實蠻水的XDDD，但是我花了蠻久才看的出來QQQ。

理論上其實我們可以透過題目的三個公式得出一些想法

• 由於 \(x^2 + y^2 + z^2 = C\)，且 \(C <= 10000\)，因此理論上 x,y,z 不會超過 100。
• \(x+y+z = A\) x,y,z 有可能會是負整數，只要最後 A 是正就好
• \(xyz=B\) 基本上 x,y,z 如果要有負整數的情況，那一定是 x,y,z 中有兩個負整數

判斷時間複雜度 \(O(100 (100))\)，不大，最後的 z 再進行反推就能夠求出答案。

OK，那可以寫了對八！讓 x,y 從 -100 ~ 100，不斷嘗試。
注意：如果 x,y,z 其中有兩個數字一樣則不被視為答案。

參考連結

[題解] UVa 11565 - Simple Equations by 巫術社的使魔群
Uva 11565 Simple Equations by louisfghbvc

心得

難度不高，稍微動點腦就可以解出來。
用來增加大家信心的題目XD。

題目程式碼

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

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
using namespace std;
int A, B, C;
int t;

int solve(){
    for(int x = -100; x < 100; x++){ //brute fouce
        for(int y = -100; y < 100; y++){
            int z = A - x -y; //反推 z
            if(x - y == 0 || y - z == 0 || x - z == 0) continue; //判斷有沒有數值相同
            if(B != z * x * y) continue; //判斷是否符合題目公式
            if(C != (x*x + y*y + z*z)) continue;  //判斷是否符合題目公式
            cout << x << ' ' << y << ' ' << z << '\n' ; //通過挑戰，可以輸出答案
            return 1;
        }
    }
    return 0;
}

int main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCAL

    cin >> t;
    while(t--){
        cin >> A >> B >> C;
        if(solve() == 0) cout << "No solution.\n"; //如果是 0 就輸出此文字。
    }

    return 0;
}