切換
舊版
前往
大廳
主題

ZeroJudge - a517: Freak大危機!!! 解題心得

Not In My Back Yard | 2019-03-28 23:39:24 | 巴幣 2 | 人氣 164

題目連結:


題目大意:
給定三正整數 x 、 y、 z (x 、 y 、 z 皆是 unsigned long long 變數型態能容納下的數字)。其中,三數的最小值與其他兩數的差值為完全平方數;且最小的數之倒數為其他兩數的倒數和。

求標準三維空間中,點(x, y, z)與原點(0, 0, 0)的距離為何?



範例輸入:
1 2 2
2 3 6
3 4 12


範例輸出:
3
7
13


解題思維:
因為這題的測資數有點多,所以直接取 x ^ 2 + y ^ 2 + z ^ 2 的平方根可能會太慢。

而題目告訴我們 x 、 y 、z 會滿足的條件,我們可以根據條件得出下列的公式(假設 x ≦ y ≦ z):
(x ^ 2 + y ^ 2 + z ^ 2) ^ (1 ÷ 2) = y + z - x

所以我們只要算 y + z - x 即可得到答案。而我們可以驗證其正確性,以下是驗證過程:
設(x ^ 2 + y ^ 2 + z ^ 2)^(1 ÷ 2) = y + z - x 是無誤的,
則 x ^ 2 + y ^ 2 + z ^ 2 = (y+z-x) ^ 2
並可推得 x ^ 2 + y ^ 2 + z ^ 2 = x ^ 2 + y ^ 2 + z ^ 2 + 2yz - 2xz - 2xy
得 yz-xz-xy = 0,推得 yz = xz + xy = x(y + z)。

最後得 yz/(y + z) = x 是題目給定的條件之一,即最小數之倒數為其他兩數之倒數和。

因為最後一式成立,又因為等量公理所以我們可以回推出原式—— y + z - x 。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作