洛谷题解 P1226 【【模板】快速幂||取余运算】

题目描述

洛谷P1226

说明

看到题解里貌似并没有Python的题解,我来发一个,共两行。

众所周知,为什么有时候洛谷er们要用Python呢?因为Python里已经包装了很多算法,用在OI中基本上等于打游戏时开外挂。虽然

对于这道题,Python 3中有一个数学函数pow(),它在help()函数中的说明是这样的:

1
2
3
4
5
pow(x, y, z=None, /)
Equivalent to x**y (with two arguments) or x**y % z (with three arguments)

Some types, such as ints, are able to use a more efficient algorithm when
invoked using the three argument form.

x**y % z,这正好就是这道题所用到的算法,所以直接调用pow(b, p, k)就OK了。一般来说,编程语言本身的库函数都会往死里优化,基本上不用担心时间复杂度的问题。(除了某些特别坑的)

最后要注意的一点就是,很多人提交Python都莫名RE,原因是Python 3的input()函数返回的是字符串,必须用int()转换为整数。如果一行有多个数字,则调用split()方法分割成多个字符串。

上代码:

1
2
a = input().split()
print(a[0] + '^' + a[1] + ' mod ' + a[2] + '=' + str(pow(int(a[0]), int(a[1]), int(a[2]))))
文章作者: Helium
文章链接: https://keepthethink.github.io/archives/3299158642/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Heliumの博客