跳到主要内容

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

链接：1969.数组元素的最小非零乘积
难度：Medium
标签：贪心、递归、数学
简介：请你算出进行以上操作 任意次 以后，nums 能得到的 最小非零 乘积。

题解 1 - python​

  • 编辑时间：2024-03-20
  • 执行用时：51ms
  • 内存消耗：16.3MB
  • 编程语言：python
  • 解法介绍：除去最大值，其他值都能两两匹配成最大值减1和1，快速计算。
def quick_mul(a: int, b: int, mod: int) -> int:
        ans = 0
        temp = a
        while b:
            if b & 1: ans = (ans + temp) % mod
            temp = (temp + temp) % mod
            b >>= 1
        return ans
    
    def quick_pow(a: int, b: int, mod: int) -> int:
        ans = 1
        temp = a
        while b:
            if b & 1: ans = quick_mul(ans, temp, mod)
            temp = quick_mul(temp, temp, mod)
            b >>= 1
        return ans
    
    class Solution:
        def minNonZeroProduct(self, p: int) -> int:
            num = 2 ** p - 1
            mod = 10 ** 9 + 7
            return quick_pow(num - 1, num // 2, mod) * num % mod