1969. 数组元素的最小非零乘积

数组元素的最小非零乘积

• 难度: medium
• 原始链接: https://leetcode.cn/problems/minimum-non-zero-product-of-the-array-elements
• 标签: 数学

解法一: 数学

go

const MOD = 1000000007

func minNonZeroProduct(p int) int {
  // (2 ^ p - 1) * (2 ^ p - 2) ^ (2 ^ (p - 1) - 1)
  base := 1 << p
  return (base - 1) % MOD * pow((base-2)%MOD, (base>>1)-1) % MOD
}

func pow(x, n int) int {
  if n == 0 {
    return 1
  }
  half := n >> 1
  halfAns := pow(x, half)
  ans := halfAns * halfAns % MOD
  if (n & 1) == 1 {
    ans = ans * x % MOD
  }
  return ans
}