分割数组使乘积互质
给你一个长度为 n 的整数数组 nums ，下标从 0 开始。
如果在下标 i 处 分割 数组，其中 0 <= i <= n - 2 ，使前 i + 1 个元素的乘积和剩余元素的乘积互质，则认为该分割 有效 。
例如，如果 nums = [2, 3, 3] ，那么在下标 i = 0 处的分割有效，因为 2 和 9 互质，而在下标 i = 1 处的分割无效，因为 6 和 3 不互质。在下标 i = 2 处的分割也无效，因为 i == n - 1 。
返回可以有效分割数组的最小下标 i ，如果不存在有效分割，则返回 -1 。
当且仅当 gcd(val1, val2) == 1 成立时，val1 和 val2 这两个值才是互质的，其中 gcd(val1, val2) 表示 val1 和 val2 的最大公约数。
示例 1：
输入：nums = [4,7,8,15,3,5]
输出：2
解释：上表展示了每个下标 i 处的前 i + 1 个元素的乘积、剩余元素的乘积和它们的最大公约数的值。
唯一一个有效分割位于下标 2 。
示例 2：
输入：nums = [4,7,15,8,3,5]
输出：-1
解释：上表展示了每个下标 i 处的前 i + 1 个元素的乘积、剩余元素的乘积和它们的最大公约数的值。
不存在有效分割。
提示：
n == nums.length
1 <= n <= 104
1 <= nums[i] <= 106
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/split-the-array-to-make-coprime-products
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路1 朴素解法
求分割部分的乘积并计算gcd判断是否互质。写的时候就发现不可能将乘积存下来，只是想写下来再慢慢优化。到最后也没有搞定。
code
class Solution {
public:
//时间复杂度O(n)可以接受
//就是乘积太大，表示不了
int findValidSplit(vector<int>& nums) {
int n = nums.size();
int before = 1,after = 1;
before *= nums[0];
for(int i = 1;i < n;i ++) after *= nums[i];
if(gcd(before,after) == 1) return 0;
for(int i = 1;i <= n-2;i ++)
{
before *= nums[i];
after /= nums[i];
if(gcd(before,after) == 1) return i;
}
return -1;
}
};
解题思路2
如果两个数互质，那么两个数的质因数分解都不会包含公共的质因数。那么题目的问题就转换为：找到最小的分割点，使得左边所有数的质因数分解和右边所有数的质因数分解并不包含公共质因数。考虑一个质数p，分割点左侧要么不包含p，要么包含所有的p。也就是枚举分割点并判断每一个质数是否都符合以上条件。时间复杂度为\(O(loglogA + n \frac{\sqrt{A}}{logA})\),A是nums中的最大数。code以后补上先好好补一下数论的知识。