題目連結:
題目大意:
給定一正整數N,代表接下來有N行測試資料。
接下來每一行有一正整數Y(1 ≦ Y ≦ 10 ^ 1, 000),求Y的平方根之值。
此題保證Y一定是完全平方數(某正整數的平方)。
範例輸入:
3
1024
7206604678144
81
範例輸出:
32
2684512
9
解題思維:
然而這題可以使用
牛頓法逼近求解。牛頓法的精神在於利用導函數(斜率),導函數(斜率)朝向的方向會比現有的解來得更精確(雖然這麼說不太符合幾何意義)。
像是今天這題,我們想找到一個X,滿足:
X ^ 2 - Y=0
其中Y就是題目給定的值。假設今天給的是Y = 64。而我們一開始猜X = 32。
根據牛頓法:
在這一題的下一個新的X值會是:
X -(X ^ 2 - 64) / (2X)
代進上式,我們可以得到新的X值為17。再迭代一次得約10.3,取整為10(在這題可以取整)。再迭代一次得到大約為8.2,取整為8。便得到了我們要的答案。
而幾何意義類似於下方的gif:
只是牛頓法需要小心使用,有可能不會收斂(這題只有Y = 0時不會收斂,可是答案可想而知)。而且也要小心取整,有機會需要再驗算一番。並且在迭代的過程時,會需要大數除法,稍微有點麻煩。
因此,本人是使用直式開方法求得解的,懶得做除法(X
最後,據說這題也可以使用二分搜求解,這樣只需要大數乘法。(不確定會不會TLE。如果測資不夠多就可以使用。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。