Leetcode # 2438. Range Product Queries of Powers

Problem

https://leetcode.com/problems/range-product-queries-of-powers

Solution

求模倒數：費馬小定理

⚠️ 用 pow(a, p – 2, p) 取代 (a ** (p – 2)) % p

(products[l – 1] ** MODULUS_MINUS_2) % MODULUS
pow(products[l – 1], MODULUS_MINUS_2, MODULUS)

1. (a ** (p – 2)) % p
   會計算完 a^p-2 (超巨大整數)，才取模 a^p-2 % c
2. pow(base, exp, mod) 的時間複雜度為 O(log(exp))

Code

• k := popcount(n) ≥ floor(log2(n)) + 1
  　== len(powers) == len(products)
• Q := len(queies)
• M := MODULUS

Time Complexity: O(log(n) + Q * log(M)) == O(log(n) + Q * 1) == O(log(n) + Q)

• O(log(n)): 構築 powers
• O(log(M)): pow(a, p – 2, p)

Space Complexity: O(k)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:
    MODULUS = 10 ** 9 + 7
    MODULUS_MINUS_2 = MODULUS - 2

    powers = deque()
    remainder = n
    max_power = 2 ** floor(log2(n))
    while max_power > 0:
      if n >= max_power:
        powers.appendleft(max_power)
        n -= max_power
      max_power //= 2
    
    products = [powers[0]]
    for i in range(1, len(powers)):
      products.append((products[-1] * (powers[i] % MODULUS)) % MODULUS)

    return [(
      products[r] * 
      (pow(products[l - 1], MODULUS_MINUS_2, MODULUS) if l > 0 else 1)
    ) % MODULUS for l, r in queries]

Last Updated on 2025/08/13 by A1go