快速幂

[编程题]快速幂

热度指数：9770 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

请你计算 $a^b\ mod\ p$ 的值。
一共有 $q$ 次询问。

输入描述:

第一行输入一个正整数  ，代表询问次数。
接下来每行输入三个正整数 ，代表一次询问。
数据范围：

输出描述:

对于每次询问，输出一个整数，代表  的值。

示例1

输入

2
2 2 6
3 4 10

输出

4
1

算法知识视频讲解

Python 3

TS9527

写了两种解法

方法一：快速幂

相较于普通的快速幂，需要进一步在乘法过程中添加求余操作

class MainActivity:

    def main(self):
        # Read the data
        q = int(input())
        for _ in range(q):
            a, b, p = map(int, filter(lambda x: len(x) > 0, input().split(' ')))
            a %= p
            result = self.__fastPower(a, b, p)
            print(result)

    def __fastPower(self, a, b, p):
        # Initialization
        bRp = bin(b)[2:][::-1]
        result = 1
        base = a
        # Traverse
        for digit in bRp:
            if digit == '1':
                result *= base
                result %= p
            base **= 2
            base %= p
        return result


if __name__ == '__main__':
    M = MainActivity()
    M.main()

方法二：递归+哈希优化

相当于用乘法结合律减少了乘方当中做乘法的次数，即每一次求一半次方再乘起来，然后用哈希记录一些中间的计算结果供复用。但是这个方法整体上还是比快速幂慢一倍有多

class MainActivity:

    def main(self):
        # Read the data
        q = int(input())
        records = dict()
        for _ in range(q):
            del records
            records = dict()
            a, b, p = map(int, filter(lambda x: len(x) > 0, input().split(' ')))
            a %= p
            result = self.__fastPower(a, b, p, records)
            print(result)

    def __fastPower(self, a, b, p, records):
        if not b:
            return 1
        if b == 1:
            return a
        halfB = b // 2
        if (a, halfB) in records:
            leftResult = records[(a, halfB)]
        else:
            leftResult = self.__fastPower(a, halfB, p, records)
            records[(a, halfB)] = leftResult
        if (a, b - halfB) in records:
            rightResult = records[(a, b - halfB)]
        else:
            rightResult = self.__fastPower(a, b - halfB, p, records)
            records[(a, b - halfB)] = rightResult
        finalResult = (leftResult % p) * (rightResult % p) % p
        return finalResult


if __name__ == '__main__':
    M = MainActivity()
    M.main()

发表于 2024-09-06 16:25:43 回复(0)