[問題] 超 大數次方運算

[nevikw39]

最近發現 Python 的整數型別原來沒有上限，對於大數的支援實在非常完善，甚至幾十位數
相乘都能幾乎瞬間求得答案，所以就想挑戰一些大數的題目，像是這題：
http://bit.ly/2H7QGHo
我是直接 a ** b 喇，這樣花了 4.8 秒。然後我就在想如何改進。先 sum = a ** (b // 2
)，再 sum *= 2，如果 b 是奇數再乘 a。但是如此一來反而要花 6.8 秒！
輸出的部分也有嘗試直接寫入 stdout.buffer 還是 4.8 秒
同一題一樣 Python 有人原本 4.7 秒變成 78 毫秒，到底怎麼辦得到啊？
下一題（http://bit.ly/2H1TuGc）測資更變態，提示說 Python 有特殊解法第一題可以在
0.1 秒內解出，第二題 Python 也有人在 0.5 秒內解出
先謝謝各位大大惹

--
Sent from my Sony Xperia XZ1

○ PiTT // PHJCI

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 77.73.67.86
※ 文章網址: https://www.ptt.cc/bbs/Python/M.1551159184.A.CEE.html
連結修正
※ 編輯: nevikw39 (77.73.67.86), 02/26/2019 13:34:49
→ s860134: 建表查表會不會比較快？
建什麼表呢？
※ 編輯: nevikw39 (106.107.176.158), 02/26/2019 22:07:20
→ s860134: Divide and Conquer: a^20 == (a^2)^10 == (a ^4) ^5
→ s860134: 不確定這思考方向對不對
→ s860134: 我思考方向好像是錯的 因為算根本沒花多少時間= =
推 alan23273850: 你有學過快速冪嗎 演算法課本去翻一翻 概念不難
推 nini200: python占便宜 哈哈哈
推 oToToT: 剛剛我寫了個快速冪然後就TLE了，我覺得應該是python IO太
→ oToToT: 慢
我也覺得是輸出太慢 可是直接寫到 stdout.buffer 也沒有比較快
→ s860134: time python -c "str(pow(10**5,10**5))" 要七秒
→ s860134: user    0m7.812s
→ s860134: 都花在轉字串...
→ s860134: 如果自幹的算法比 python 內建還快不就取代掉惹
Python 到底有沒有什麼特殊解呢？
不然自己寫大數用 c++ 應該更有效率
字串的部分查了一下，% > .format > str() 的樣子，可是還是 4.8 秒
※ 編輯: nevikw39 (106.107.176.158), 02/27/2019 00:18:20
推 alen84204: 菜雞連AC都寫不出QQ
a 大你好，第一題我是有 AC 喇，只是很好奇其他人怎麼有辦法速解，如果你有好方法還請
不吝分享
※ 編輯: nevikw39 (101.136.64.8), 02/27/2019 07:47:44
推 alan23273850: 那如果試試這個？https://www.python123.io/index/
→ alan23273850: topics/algorithm_100_days/100-days-of-algorithm
→ alan23273850: s-10
Karatsuba 法似乎多用於乘法，然後再用迴圈，回去試試有沒有比較快
※ 編輯: nevikw39 (101.137.163.39), 02/27/2019 17:31:11
→ edwar: from decimal import *; getcontext().prec=700000;
→ edwar: print(Decimal(10**5) ** (10**5))
實在非常感謝 e 大提供的想法，沒想到 decimal 也可以這麼用
只是你應該是指 Decimal(a) ** Decimal(b) ，醬子才是 decimal 的運算 XD
※ 編輯: nevikw39 (106.107.176.158), 02/28/2019 08:30:42
→ s860134: 上面 e 大寫法沒有問題，decimal 實作上有 type casting
→ s860134: https://goo.gl/iHMtVr
→ s860134: 3.4 https://goo.gl/QNofY9，可以從 Decimal.__pow__ 查