普通電腦可以做網(wǎng)站服務(wù)器韓國最新新聞
思路詳解:
請注意,本題解用到了非整數(shù)計算,也就是說性能可能不如整數(shù)運算,但是易于實現(xiàn),追求最優(yōu)解的大佬不建議觀看本題解。
這個題看似簡單,但是由于涉及到了平方操作,不用高精度根本存不下,然后如果你要用高精度的話又會 T L E TLE TLE 而且巨難寫。
嘗試使用對數(shù)科技,根據(jù)高中數(shù)學(xué)的知識我們可以知道 log ? ( n ? n ) = 2 × log ? n \log(n* n) = 2 \times \log n log(n?n)=2×logn,但是注意到 n ≤ 2 × 1 0 5 n \le 2 \times 10^5 n≤2×105,所以就算將平方操作轉(zhuǎn)化成了 × 2 \times 2 ×2 操作仍然無法通過本題。
然后做這道題的時候筆者想到這里就覺得這道題不可做,然后果斷放棄了。。
但事實上,對數(shù)科技并不是只能使用一次,我們可以通過對數(shù)的轉(zhuǎn)化將 × 2 \times 2 ×2 轉(zhuǎn)化成 + 2 + 2 +2,即 log ? ( n × 2 ) = log ? n + log ? 2 \log (n \times 2) = \log n + \log 2 log(n×2)=logn+log2,因此,我們就根據(jù)上述兩個等式成功將平方操作轉(zhuǎn)化成了 + 2 + 2 +2? 操作。
然后就做完了。
tip: 由于使用了非整數(shù)的運算,所以判斷是否等于 0 的時候建議和 eps 作比較,防止出現(xiàn)精度上的問題,即出現(xiàn)了誤差。