专栏首页大白技术控的技术自留地C#版(击败100.00%的提交) - Leetcode 372. 超级次方 - 题解

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

Leetcode 372. 超级次方 - 题解

372.Super Pow

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

题目描述


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

示例 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,nxnxn^{x} mod n = 0。 如果p是素数,但不是b的约数,则由费马小定理 (apapa^p≡a (mod p)),可得a⋅bp−1a⋅bp−1a\cdot b^{p-1} mod p = a mod p。

逆运算: [(-a mod n) +(a mod n) ] mod n = 0。 b−1b−1b^{-1} mod n被称为”模逆元”,整数 a 对模数 n 之模逆元存在的充分必要条件是 a 和 n 互素,若此模逆元存在,在模数 n 下的除法可以用和对应模逆元的乘法来达成,[( b−1b−1b^{-1}mod n) (b mod n)] mod n = 1。

分配率: (a + b) mod n = [(a mod n) +(b mod n) ] mod n。 a⋅ba⋅ba\cdot b mod n = [(a mod n) (b mod n) ] mod n。 d mod(a⋅b⋅ca⋅b⋅ca\cdot b\cdot c) =(d mod a) + a [(d \ a) mod b] + a⋅ba⋅ba\cdot b [(d \ a \ b) mod c],其中\是欧几里德除法的商的算子。 c mod(a + b) =(c mod a) + [b⋅cb⋅cb\cdot c (a + b) ] mod b - [b⋅cb⋅cb\cdot c (a + b) ] mod a。

除法 : A/B abab\frac{a}{b}mod n = [(a mod n) (b−1b−1b^{-1} mod n) ] mod n,当b和n互质时,右边被定义。反之亦然。

相乘后的逆(Inverse multiplication)

[(a⋅ba⋅ba\cdot b mod n) (b−1b−1b^{-1} mod n) ] mod n = a mod n。

特殊性质: x % 2n2n2^n == x & (2n−12n−12^n-1)

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

此题需用到分配率中的: a⋅ba⋅ba\cdot b mod n = [(a mod n) (b mod n) ] mod n

已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;
    }
}

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • C++版 - 剑指offer 面试题32:从1到n整数中1出现的次数(leecode233. Number of Digit One) 题解

    剑指offer 面试题32:从1到n整数中1出现的次数(Leecode233. Number of Digit One)

    Enjoy233
  • C#版 - HDUoj 5391 - Zball in Tina Town(素数) - 题解

    在线提交: http://acm.hdu.edu.cn/showproblem.php?pid=5391 Time Limit: 3000/1500 M...

    Enjoy233
  • C#版 - LeetCode 148. Sort List 解题报告(归并排序小结)

    提交网址: https://leetcode.com/problems/sort-list/

    Enjoy233
  • 非对称加密技术- RSA算法数学原理分析

    Tiny熊
  • HDU 1104 Remainder(BFS 同余定理)

    题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=1104 在做这道题目一定要对同余定理有足够的了解,所以对这道...

    ShenduCC
  • Apache 性能配置优化

    最近在进行apache性能优化设置。在修改apache配置文件之前需要备份原有的配置文件夹conf,这是网站架设的好习惯。本文讲述的apache配置调优均是在r...

    刘远飞
  • go modules:使用 mod 管理项目依赖包,通过vendor实现一键分发编译包

    在go语言1.11版本之前,没有modules机制,所有软件包都在安装在$GOPATH/src目录下。不同项目如果引用了同一个软件包的不同版本,就会造成编译麻烦...

    石桥码农
  • HDU----(4549)M斐波那契数列(小费马引理+快速矩阵幂)

    M斐波那契数列 Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (J...

    Gxjun
  • OMRONFZ系列视觉与ABB机器人的通信

    ABB与OMRON之间的通信,本例采用以太网TCP无协议模式通信。通过以太网由ABB机器人程序控制ONRON视觉的场景切换,拍照判断及其判断数据的 接收。 ?...

    EdenChen
  • Java并发学习之定时任务的几种玩法

    Java中创建和玩转定时任务 定时任务,在日常工作中,可以说是一个算是一个常见的需求场景,比如定时数据校验,数据报表输出,报警等 0. 前言 前面一篇博文《J...

    小灰灰

扫码关注云+社区

领取腾讯云代金券