leetcode Super Pow

leetcode Super Pow

Your task is to calculate ab mod 1337 where a is a positive integer and b is an extremely large positive integer given in the form of an array.

Example1:

Example2:

题目地址:leetcode Super Pow

题意:给定数a和用数组表示的一个很大的数b,求a^b % 1337

思路:

一个数e可以写成如下形式:

e=\sum _{i=0}^{n-1}a_{i}2^{i}

显然,对于b的e次方,有:

b^{e}=b^{\left(\sum _{i=0}^{n-1}a_{i}2^{i}\right)}=\prod _{i=0}^{n-1}\left(b^{2^{i}}\right)^{a_{i}}

c\equiv \prod _{i=0}^{n-1}\left(b^{2^{i}}\right)^{a_{i}}\ ({\mbox{mod}}\ m)

 

此外,还有:

c mod m = (a ⋅ b) mod m  = [(a mod m) ⋅ (b mod m)] mod m

参照wiki :https://en.wikipedia.org/wiki/Modular_exponentiation

看懂了上面的式子后,回到此题,此题b用数组表示,其实就是把上面的数e的2改为10即可。

因此,用Python可以得到此题的写法为:

 

当然,我们可以用快速幂来加速

C++

Java

 

 

本题是leetcode 372 Sum of Two Integers 题解

更多题解可以查看:https://www.hrwhisper.me/leetcode-algorithm-solution/

 

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode Super Pow
本文地址:https://www.hrwhisper.me/leetcode-super-pow/

听说帅的人已经打赏了

Leetcode , , , , . permalink.

4 thoughts on “leetcode Super Pow

Leave a Reply

Your email address will not be published. Required fields are marked *