【分解质因数 差分数组】2584. 分割数组使乘积互质

class Solution {
public:
  int findValidSplit(vector<int>& nums) {
    auto vPrime = CreatePrime(1'000);
    const int iMax = *std::max_element(nums.begin(),nums.end());
    vector<vector<int>> indexs(iMax+1);
    for (int i = 0; i < nums.size(); i++) {
      int tmp = nums[i];
      for (auto& iPri : vPrime) {
        if (iPri * iPri > tmp) { break; }
        if (0 == tmp % iPri) { indexs[iPri].emplace_back(i); }
        while ((0 == tmp % iPri)) {
          tmp /= iPri;
        }
      }
      if( tmp > 1){ indexs[tmp].emplace_back(i); }
    }
    vector<int> vDiff(nums.size() );
    for (int i = 0; i <= iMax; i++) {
      if (indexs[i].size() < 2) { continue; }
      vDiff[indexs[i].front()]++;
      vDiff[indexs[i].back()]--;
    }
    int iSum = 0;
    for (int i = 0; i +1< nums.size(); i++) {
      iSum += vDiff[i];
      if (0 == iSum) { return i; }
    }
    return -1;
  }
};

template<class T>
void Assert(const T& t1, const T& t2)
{
    assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
    if (v1.size() != v2.size())
    {
        assert(false);
        return;
    }
    for (int i = 0; i < v1.size(); i++)
    {
        Assert(v1[i], v2[i]);
    }
}
int main()
{
  vector<int> nums;
  {
    Solution sln;
    nums = { 4, 7, 8, 15, 3, 5 };
    auto res = sln.findValidSplit(nums);
    Assert(2, res);
  }
  {
    Solution sln;
    nums = { 4,7,15,8,3,5 };
    auto res = sln.findValidSplit(nums);
    Assert(-1, res);
  }
}