[ACM ] [WA] 10023 Square Root
UVa 10023 Square Root
http://www.tcgs.tc.edu.tw/~sagit/luckycat/q10023.htm
給你一個整數Y，請你求出根號Y的值。
Input :
第1列有一個整數 n，代表接下來有n列測試資料。
每列測試資料有一個正整數Y（1 <= Y <=10^1000）。
我們保證Y一定是某一個正整數的平方。
Output :
每一筆測試資料請輸出根號Y的值，測試資料之間請輸出一空白行。
//========== Sample input
3
1024
7206604678144
81
//========== Sample Output
32
2684512
9
------------------------------------
資料結構上採用「DJWS的網路日誌」中所述方式，以陣列將數字反序儲存，網頁如下
http://www.csie.ntnu.edu.tw/~u91029/BigNumber.html
且只先用一格存一位數的方式
找平方根時採用直覺的直式開方法，唯獨在決定下一位數時先用前幾位去猜
想法舉例如下：
假設 num = (9876504321 * 9876504321) = 97545337602731671041 (20位數)
先取前幾位可以放的進int的部分，若num為偶數就取偶數位, 奇數就取奇數位
用普通的sqrt處理
得到 result = sqrt(97543376) = 9876
result^2 = 97535376
接下來將前幾位取下, 並且先減掉目前算出來的result^2
97545337 (dividend)
-97535376
---------
9961
再來每次往後拿兩位 //=== 以下重複直到算出square root的每一位數 ===
996160 (dividend)
並且希望求出result的下一位:X, 此時由於 9876X * 9876X <= 9754533760
(result*10+X)(result*10+X) <= 9754533760
9754533760 - 100*result*result >= 20*result*X + X*X
所以我們知道 dividend >= 20*X*result 用這個去猜X
X <= (dividend/result)/20
其中dividend和result皆為大數, 不能直接做除法, 因此試圖捨棄一些精確度轉成int
猜 X = (int(dividend)/int(result))/20 + 1 雖然不精確, 但應該相差不遠
然後用這個猜的X去試試看是否 X*X + 20*result <= dividend
如果不是就將X遞減, 然後重複測試
-----
測了蠻多測資都是正確的, 不知道什麼情況下會錯誤 或是code的哪裡出了問題呢?
http://codepad.org/OOwvk2RB
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 112.104.11.16
※ 編輯: bc5678 來自: 112.104.11.16 (09/26 23:29)
→
09/27 06:57, , 1F
09/27 06:57, 1F
→
09/27 10:48, , 2F
09/27 10:48, 2F