吃++中一堆数的子序列

题目描述：

给定一个长度为n的正整数序列 a1,a2,…,an，你需要选出一个非空子序列，使得这个子序列中的数的乘积模 109+7 的值最大。

数据范围：1≤n≤105，1≤ai≤103。

样例：

输入：

3

1 2 3

输出：

6

输入：

4

1 2 3 4

输出：

24

算法1：

(暴力枚举) $O(n^2)$

枚举所有子序列，计算乘积并取模，记录最大值。

时间复杂度

枚举子序列需要 $O(n^2)$，计算乘积需要 $O(n)$，所以总时间复杂度为 $O(n^3)$。

C++ 代码

算法2：

(贪心) $O(n)$

由于模数为质数，我们可以使用费马小定理求乘法逆元。

对于每个数，我们可以先把它分解质因数，然后对于每个质因子，我们可以计算出它在所有子序列中出现的次数，这个次数是 $2^n-1$，其中 $n$ 是这个质因子出现的次数。我们可以使用快速幂计算 $2^n-1$，然后乘上这个质因子，最后再将所有质因子的积取模，就得到了最大乘积。

时间复杂度

每个数需要分解质因数，时间复杂度为 $O(\sqrt{n}\log n)$，计算每个质因子的次数需要用到快速幂，时间复杂度为 $O(\log p)$，总时间复杂度为 $O(n\sqrt{n}\log n)$。

C++ 代码