這題可以說是 e024 的強化版本
實作時必須使用 C++的型態 __int128 保證最小化進位次數達到題目規定的時間
但 __int128 的最大值是 170141183460469231731687303715884105727(39位數)且題目保證結果輸出的位數長度不會大於1e6,
我個人反推最安全的基底應該是1e16
將最大長度1e6拆成最糟糕的兩個大數相乘時,兩者各自長度是5e5,換句話說必須保證5e5個同一個位數的數值累加時不會發生溢位問題
(39-"6")/2=16.5,使用17可能有溢位風險...
但礙於題目的最低時間限制必須在5s內,只能使用基底是1e17
(希望可以開放1e16也能通過該筆測試)
如果我錯估基底的計算方式也請題主給予修正,謝謝
這題可以說是 e024 的強化版本
實作時必須使用 C++的型態 __int128 保證最小化進位次數達到題目規定的時間
但 __int128 的最大值是 170141183460469231731687303715884105727(39位數)且題目保證結果輸出的位數長度不會大於1e6,
我個人反推最安全的基底應該是1e16
將最大長度1e6拆成最糟糕的兩個大數相乘時,兩者各自長度是5e5,換句話說必須保證5e5個同一個位數的數值累加時不會發生溢位問題
(39-"6")/2=16.5,使用17可能有溢位風險...
但礙於題目的最低時間限制必須在5s內,只能使用基底是1e17
(希望可以開放1e16也能通過該筆測試)
如果我錯估基底的計算方式也請題主給予修正,謝謝
對不起,我為了卡Python一般解法,把C++1e16也卡掉了
不過我沒有放讓17溢位的測資就是了
我會想辦法調整測資與時間
這題可以說是 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