作者nevikw39
看板Python
标题[问题] 超 大数次方运算
时间Tue Feb 26 13:32:58 2019
最近发现 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://webptt.com/cn.aspx?n=bbs/Python/M.1551159184.A.CEE.html
连结修正
※ 编辑: nevikw39 (77.73.67.86), 02/26/2019 13:34:49
1F：→ s860134: 建表查表会不会比较快？02/26 20:24
建什麽表呢？
※ 编辑: nevikw39 (106.107.176.158), 02/26/2019 22:07:20
2F：→ s860134: Divide and Conquer: a^20 == (a^2)^10 == (a ^4) ^502/26 22:43
3F：→ s860134: 不确定这思考方向对不对02/26 22:46
4F：→ s860134: 我思考方向好像是错的 因为算根本没花多少时间= =02/26 23:29
5F：推 alan23273850: 你有学过快速幂吗 演算法课本去翻一翻 概念不难02/26 23:42
6F：推 nini200: python占便宜 哈哈哈02/26 23:45
7F：推 oToToT: 刚刚我写了个快速幂然後就TLE了，我觉得应该是python IO太02/26 23:46
8F：→ oToToT: 慢02/26 23:47
我也觉得是输出太慢 可是直接写到 stdout.buffer 也没有比较快
9F：→ s860134: time python -c "str(pow(10**5,10**5))" 要七秒02/27 00:02
10F：→ s860134: user 0m7.812s02/27 00:02
11F：→ s860134: 都花在转字串...02/27 00:02
12F：→ s860134: 如果自干的算法比 python 内建还快不就取代掉惹02/27 00:04
Python 到底有没有什麽特殊解呢？
不然自己写大数用 c++ 应该更有效率
字串的部分查了一下，% > .format > str() 的样子，可是还是 4.8 秒
※ 编辑: nevikw39 (106.107.176.158), 02/27/2019 00:18:20
13F：推 alen84204: 菜鸡连AC都写不出QQ02/27 02:21
a 大你好，第一题我是有 AC 喇，只是很好奇其他人怎麽有办法速解，如果你有好方法还请
不吝分享
※ 编辑: nevikw39 (101.136.64.8), 02/27/2019 07:47:44
15F：→ alan23273850: topics/algorithm_100_days/100-days-of-algorithm02/27 11:09
16F：→ alan23273850: s-1002/27 11:09
Karatsuba 法似乎多用於乘法，然後再用回圈，回去试试有没有比较快
※ 编辑: nevikw39 (101.137.163.39), 02/27/2019 17:31:11
17F：→ edwar: from decimal import *; getcontext().prec=700000;02/27 22:41
18F：→ edwar: print(Decimal(10**5) ** (10**5)) 02/27 22:41
实在非常感谢 e 大提供的想法，没想到 decimal 也可以这麽用
只是你应该是指 Decimal(a) ** Decimal(b) ，酱子才是 decimal 的运算 XD
※ 编辑: nevikw39 (106.107.176.158), 02/28/2019 08:30:42
19F：→ s860134: 上面 e 大写法没有问题，decimal 实作上有 type casting 02/28 13:04