372.超级次方

链接：372.超级次方
难度：Medium
标签：数学、分治
简介：你的任务是计算 ab 对 1337 取模，a 是一个正整数，b 是一个非常大的正整数且会以数组形式给出。

题解 1 - typescript

• 编辑时间：2021-12-05
• 执行用时：84ms
• 内存消耗：39.7MB
• 编程语言：typescript
• 解法介绍：99^(2345) === (99^234)^10 * 99^5。

const MOD = 1337;
function pow(a: number, b: number) {
  let ans = 1;
  while (b--) ans = (ans * a) % MOD;
  return ans;
}
function superPow(a: number, b: number[]): number {
  let ans = 1;
  for (let i = 0; i < b.length; i++) {
    ans = (pow(ans, 10) * pow(a, b[i])) % MOD;
  }
  return ans;
}

题解 2 - typescript

• 编辑时间：2021-12-11
• 执行用时：152ms
• 内存消耗：44.3MB
• 编程语言：typescript
• 解法介绍：拆解次方，快速幂相乘。

const mod = 1337n;
function pow(a: bigint, b: bigint): bigint {
  let ans = 1n;
  let num = a;
  while (b) {
    if (b & 1n) ans = (ans * num) % mod;
    num = (num * num) % mod;
    b >>= 1n;
  }
  return ans;
}
function superPow(a: number, b: number[]): number {
  let ans = 1n;
  const biga = BigInt(a);
  for (const num of b) {
    ans = (pow(ans, 10n) * pow(biga, BigInt(num))) % mod;
  }
  return Number(ans);
}