Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediummath-number-theory

Super Pow

Problem (restated)

Compute a^b mod 1337, where the exponent b is given as an array of decimal digits (too large to fit in a 64-bit int).

Intuition

a^[1,0,2] = ((a^1)^10 · a^0)^10 · a^2. Scan digits left to right: at each digit, raise the running answer to the 10th and multiply by a^digit, all mod 1337. Each small power uses the same binary exponentiation as LC 50.

Approaches

Digit-by-digit modPow

Unverified

Time O(d log 10)Space O(1)

Idea. ans = 1. For each digit d of b: ans = modPow(ans, 10) * modPow(a, d) % 1337. modPow is square-and-multiply with % 1337 after every multiply.

Walkthrough. a = 2, b = [1,0] → after 1: 2; after 0: 2^10 = 1024. a = 2, b = [3] → 8.

Trade-offs. Take % 1337 on the base first. C#/JS must multiply in 64-bit (or number) before reducing — int * int overflows. Euler’s theorem (φ(1337)=1140) is optional and needs gcd(a, 1337) = 1.

Solution

const MOD = 1337;

function modPow(base: number, exp: number): number {
  let b = ((base % MOD) + MOD) % MOD;
  let r = 1;
  while (exp > 0) {
    if (exp % 2 === 1) r = (r * b) % MOD;
    b = (b * b) % MOD;
    exp = Math.floor(exp / 2);
  }
  return r;
}

export function superPow(a: number, b: number[]): number {
  let ans = 1;
  for (const d of b) {
    ans = (modPow(ans, 10) * modPow(a, d)) % MOD;
  }
  return ans;
}

const MOD = 1337;

function modPow(base: number, exp: number): number {
  let b = ((base % MOD) + MOD) % MOD;
  let r = 1;
  while (exp > 0) {
    if (exp % 2 === 1) r = (r * b) % MOD;
    b = (b * b) % MOD;
    exp = Math.floor(exp / 2);
  }
  return r;
}

export function superPow(a: number, b: number[]): number {
  let ans = 1;
  for (const d of b) {
    ans = (modPow(ans, 10) * modPow(a, d)) % MOD;
  }
  return ans;
}

Template connection

Modular-exponent shape of Math & Number Theory: LC 50’s square-and-multiply, with a modulus and a digit-array exponent. % m after every multiply.

Reflection

Read b from the left. Each digit does ans = modPow(ans, 10) * modPow(a, d) % 1337.
modPow reduces modulo 1337 after every multiply. Reduce a before you start.
Exponent [0] answers 1. 1337 is not prime, so square-and-multiply is enough; Fermat does not apply.