C#版(击败100.00%的提交) - Leetcode 372. 超级次方 - 题解

版权声明: 本文为博主Bravo Yeung(知乎UserName同名)的原创文章，欲转载请先私信获博主允许，转载时请附上网址
http://blog.csdn.net/lzuacm。

Leetcode 372. 超级次方 - 题解

372.Super Pow

在线提交: https://leetcode.com/problems/super-pow/

题目描述

你的任务是计算

示例 1:

a = 2
b = [3]

结果: 8

示例 2:

a = 2
b = [1,0]

结果: 1024

示例 3:

a = 2147483647
b = [2,0,0]
结果: 1198

致谢：

特别感谢 @Stomach_ache 添加这道题并创建所有测试用例。

题目难度：Medium
通过次数：77
提交次数：399
相关话题数学
相似题目 Pow(x, n)

相关知识与思路:
直接用字符串处理的话，对corner case(示例3)会越界~

public class Solution
{
    public int SuperPow(int a, int[] b)
    {
        int res = 0;
        StringBuilder sb = new StringBuilder();
        foreach (var item in b)
            sb.Append(item);
        int.TryParse(sb.ToString(), out int p);
        var val = (int) Math.Pow(a, p);
        res = val - (val / 1337)*1337;

        return res;
    }
}

因此需利用模运算的性质来优化~

模运算的相关性质：

换算公式
有些模运算操作可以被因式分解或展开，类似于其他的数学运算。这在密码证明中应用很广泛，例如Diffie-Hellman(迪菲-赫尔曼)秘钥交换算法。

恒等式/同一性(Identity)：
(a mod n) mod n = a mod n。
对于任意正整数x，

逆运算：
[(-a mod n) +(a mod n) ] mod n = 0。

分配率：
(a + b) mod n = [(a mod n) +(b mod n) ] mod n。
。
d mod(

除法：
A/B

相乘后的逆(Inverse multiplication)：

[(

特殊性质:
x %

另外，与之相关的一个概念是同余(Congruence relation)。

此题需用到分配率中的:

已AC代码:

public class Solution
{
    const int Mod0 = 1337;
    public int SuperPow(int a, int[] b)
    {
        if (b.Length == 0)
            return 1;

        var res = 1;
        for (int i = b.Length - 1; i >= 0; i--)
        {
            res = powMod(a, b[i]) * res % Mod0;
            a = powMod(a, 10);
        }

        return res;
    }

    private int powMod(int a, int m)
    {
        a %= Mod0;
        int result = 1;
        for (int i = 0; i < m; i++)
            result = result * a % Mod0;

        return result;
    }
}

Rank:
You are here!
Your runtime beats 100.00% of csharp submissions.

按理说，如果将a%m改为a-(a/m)*m，代码运行速度会变快些，结果变得更慢了，而且运行时间不稳定。

public class Solution
{
    const int Mod0 = 1337;
    public int SuperPow(int a, int[] b)
    {
        if (b.Length == 0)
            return 1;

        var res = 1;
        for (int i = b.Length - 1; i >= 0; i--)
        {
            var powModResult = powMod(a, b[i]) * res;
            res = powModResult - (powModResult / Mod0) * Mod0;
            a = powMod(a, 10);
        }

        return res;
    }

    private int powMod(int a, int m)
    {
        a = a - (a / Mod0) * Mod0;
        int result = 1;
        for (int i = 0; i < m; i++)
            result = result * a - (result * a / Mod0) * Mod0;

        return result;
    }
}