Readme

2584.Split-the-Array-to-Make-Coprime-Products

因为本题里nums的数值都很大，连乘几个数就会溢出，所以我们无法通过直接计算乘积来解题。

既然是互质，一个很自然的想法就是从质因数入手。如果某个质因数p在nums里存在的范围是从[a:b]，那么显然，我们所寻找的前缀切割位置不能在[a:b]的中间，否则切割前后的两部分就会有公约数p。

所以基本的算法思想就是。考察每个元素，记录它的所有质因数。然后对每种质因数，我们记录它在nums里出现的范围，只要记录第一次出现和最后一次出现的位置即可，记做一个区间。这样，我们可以收集到很多的区间。之后我们要寻找某个前缀的位置，使其不能切割任何一个区间。怎么实现呢？很明显我们可以用扫描线（差分数组）来做。对于一个区间[a,b]，我们就记录差分diff[a]+=1, diff[b]-=1，这样当我们从前往后的积分值第一次出现零的时候，就表示该处没有落在任何区间里面，即是符合条件的前缀截止位置。

时间复杂度分析：遍历所有元素是o(N)，每个元素的分解质因数的复杂度是sqrt(M)，M是数值的大小，故大概是1e4*sqrt(1e6) = 1e7，勉强可以接受。事实上，如果先把所有的质因数提前计算出来，能够帮助更快地分解质因数。