#16767: C++ 解題時的 base 問題


rollfc (胖胖貓)

學校 : 國立清華大學
編號 : 81012
來源 : [49.216.18.187]
最後登入時間 :
2024-11-10 10:25:04
e035. 少年πの超大數運算(2) -- π | From: [115.82.65.219] | 發表日期 : 2019-02-06 00:32

這題可以說是 e024 的強化版本

實作時必須使用 C++的型態 __int128 保證最小化進位次數達到題目規定的時間

但 __int128 的最大值是 170141183460469231731687303715884105727(39位數)且題目保證結果輸出的位數長度不會大於1e6,

我個人反推最安全的基底應該是1e16

將最大長度1e6拆成最糟糕的兩個大數相乘時,兩者各自長度是5e5,換句話說必須保證5e5個同一個位數的數值累加時不會發生溢位問題

(39-"6")/2=16.5,使用17可能有溢位風險...

但礙於題目的最低時間限制必須在5s內,只能使用基底是1e17

(希望可以開放1e16也能通過該筆測試)

如果我錯估基底的計算方式也請題主給予修正,謝謝

 
#16772: Re:C++ 解題時的 base 問題


314159265358979323846264338327 ... (少年π)

學校 : 臺北市私立延平高級中學
編號 : 69058
來源 : [223.136.179.30]
最後登入時間 :
2024-04-29 19:11:35
e035. 少年πの超大數運算(2) -- π | From: [111.71.59.157] | 發表日期 : 2019-02-06 09:44

這題可以說是 e024 的強化版本

實作時必須使用 C++的型態 __int128 保證最小化進位次數達到題目規定的時間

但 __int128 的最大值是 170141183460469231731687303715884105727(39位數)且題目保證結果輸出的位數長度不會大於1e6,

我個人反推最安全的基底應該是1e16

將最大長度1e6拆成最糟糕的兩個大數相乘時,兩者各自長度是5e5,換句話說必須保證5e5個同一個位數的數值累加時不會發生溢位問題

(39-"6")/2=16.5,使用17可能有溢位風險...

但礙於題目的最低時間限制必須在5s內,只能使用基底是1e17

(希望可以開放1e16也能通過該筆測試)

如果我錯估基底的計算方式也請題主給予修正,謝謝

對不起,我為了卡Python一般解法,把C++1e16也卡掉了
不過我沒有放讓17溢位的測資就是了

我會想辦法調整測資與時間

 
#16773: Re:C++ 解題時的 base 問題


314159265358979323846264338327 ... (少年π)

學校 : 臺北市私立延平高級中學
編號 : 69058
來源 : [223.136.179.30]
最後登入時間 :
2024-04-29 19:11:35
e035. 少年πの超大數運算(2) -- π | From: [111.71.59.157] | 發表日期 : 2019-02-06 09:56

這題可以說是 e024 的強化版本

實作時必須使用 C++的型態 __int128 保證最小化進位次數達到題目規定的時間

但 __int128 的最大值是 170141183460469231731687303715884105727(39位數)且題目保證結果輸出的位數長度不會大於1e6,

我個人反推最安全的基底應該是1e16

將最大長度1e6拆成最糟糕的兩個大數相乘時,兩者各自長度是5e5,換句話說必須保證5e5個同一個位數的數值累加時不會發生溢位問題

(39-"6")/2=16.5,使用17可能有溢位風險...

但礙於題目的最低時間限制必須在5s內,只能使用基底是1e17

(希望可以開放1e16也能通過該筆測試)

如果我錯估基底的計算方式也請題主給予修正,謝謝

對不起,我為了卡Python一般解法,把C++1e16也卡掉了
不過我沒有放讓17溢位的測資就是了

我會想辦法調整測資與時間

感謝rollfc指正,已將時限放寬至5.5s


 
ZeroJudge Forum