Super Pow

Problem (yeniden ifade)

a^b mod 1337 hesapla; üs b ondalık basamak dizisi olarak verilir (64-bit int’e sığmaz).

Sezgi

a^[1,0,2] = ((a^1)^10 · a^0)^10 · a^2. Basamakları soldan sağa tara: her basamakta çalışan cevabı 10. üsse yükselt ve a^basamak ile çarp, hepsi mod 1337. Küçük üsler LC 50 ile aynı ikili üs alma.

Yaklaşımlar

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

Şablon bağlantısı

Math & Number Theory’nin modular-exponent şekli: LC 50’nin kare-ve-çarp’ı, modulus ve basamak-dizi üs ile. Her çarpımdan sonra % m.

Yansıma

• b soldan sağa. Her basamakta ans = modPow(ans, 10) * modPow(a, d) % 1337.
• modPow her çarpımdan sonra 1337’ye indirir. a önce moda çekilir.
• Üs [0] ise cevap 1. 1337 asal değil; Fermat değil, kare-ve-çarp yeter.