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 添加这道题并创建所有测试用例。
相关知识与思路: 直接用字符串处理的话，对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.