[Swift]LeetCode372.超级次方|SuperPow

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10277784.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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

Example 1:

Input: a = [3]
Output: 8

Example 2:

Input: a = [1,0]
Output: 1024

你的任务是计算 ab 对 1337 取模，a 是一个正整数，b 是一个非常大的正整数且会以数组形式给出。

示例 1:

输入: a = 2, b = [3]
输出: 8

示例 2:

输入: a = 2, b = [1,0]
输出: 1024

68ms

 1 class Solution {
 2     let mod = 1337
 3     func superPow(_ a: Int, _ b: [Int]) -> Int {
 4         guard b.count > 0 else {
 5             return 1
 6         }
 7         var num = 1
 8         var tmpA = a
 9         for tmpNum in b.reversed() {
10             num = powMod(tmpA, tmpNum) * num % mod
11             tmpA = powMod(tmpA, 10);
12         }
13         return num
14     }
15     
16     private func powMod(_ a: Int, _ m: Int) -> Int{
17         let tmpA = a % mod
18         var result = 1
19         for _ in 0 ..< m {
20             result = result * tmpA % mod
21         }
22         return result
23     }
24 }

76ms

 1 class Solution {
 2     func superPow(_ a: Int, _ b: [Int]) -> Int {
 3         var rst: Int = 1;
 4         var x = a;
 5         for n in b {
 6             rst = newPow(rst, 10) * newPow(x, n) % 1337;
 7         }
 8         return rst;
 9     }
10     
11     func newPow(_ x: Int, _ n: Int) -> Int {
12         if n == 0{
13             return 1;
14         }
15         if n == 1{
16             return x % 1337;
17         }
18         
19         return newPow(x % 1337, n / 2) * newPow(x % 1337, n - n / 2) % 1337;
20     }
21 }

108ms

 1 class Solution {
 2     func superPow(_ a: Int, _ b: [Int]) -> Int {
 3         
 4         var result:Int=1
 5         
 6         for i in 0...b.count-1 {
 7             result = self.pow(result, 10) * pow(a, b[i]) % 1337
 8         }
 9         
10         return result;
11     }
12     func pow(_ x: Int ,_ n: Int) -> Int {
13         if (n == 0) {return 1}
14         if (n == 1) {return x % 1337}
15         return pow(x % 1337, n / 2) * pow(x % 1337, n - n / 2) % 1337;
16 
17     }
18 }

168ms

 1 class Solution {
 2     func superPow(_ a: Int, _ b: [Int]) -> Int {
 3         var res:Int = 1
 4         for i in 0..<b.count
 5         {
 6             res = pow(res, 10) * pow(a, b[i]) % 1337
 7         }
 8         return res
 9     }
10     
11     func pow(_ x:Int,_ n:Int) -> Int
12     {
13         if n == 0 {return 1}
14         if n == 1 {return x % 1337}
15         return pow(x % 1337, n / 2) * pow(x % 1337, n - n / 2) % 1337
16     }
17 }