当前位置:首页 > 递归 > 正文
SSOJ1455取余运算
2096+

题目大意:输入b,p,k的值,求bp mod k 的值。 其中b,p,k*k 为长整形正数。

输入

输入b,p,k的值

输出

输出bp mod k 的值

样例输入

2 10 9

样例输出

2^10 mod 9=7

解题思路

bp mod k,bp会超过基本数据类型,但可以通过取模避免使用高精度。然而p为长整型,如果p=1e9,乘1e9次,就会超时。我们可以考虑用log级别的算法。

如果p是偶数,那么b^p = b^(2*p/2) = (b^2) ^ (p/2),这样计算p次就转化成p/2次了;如果p是奇数,b^p = b ^ (1+p-1) = b * b ^ (p-1),次幂就转化成偶数了。就这样,偶数可以减半,奇数1次可以转成偶数,不管是奇数还是偶数,都可以在2次以内将次幂减半。就这样不停/2和-1,b最终会变为0,因此结束条件为b=0,0次幂返回1。时间复杂度O(log(p))。

程序实现

About

坚决不Copy代码!

本文标签:,,,,,

SSOJ1455取余运算:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!