class Solution {
public int findValidSplit(int[] nums) {
int n = nums.length;
var left = new HashMap<Integer, Integer>(); // left[p] 表示质数 p 首次出现的下标
var right = new int[n]; // right[i] 表示左端点为 i 的区间的右端点的最大值
for (int i = 0; i < n; i++) {
int x = nums[i];
for (int d = 2; d * d <= x; ++d) // 分解质因数
if (x % d == 0) {
if (left.containsKey(d))
right[left.get(d)] = i; // 记录左端点对应的右端点的最大值
else
left.put(d, i); // 第一次遇到质数 d
for (x /= d; x % d == 0; x /= d) ;
}
if (x > 1)
if (left.containsKey(x))
right[left.get(x)] = i;
else
left.put(x, i);
}
for (int l = 0, maxR = 0; l < n; l++) {
if (l > maxR) // 最远可以遇到 maxR
return maxR; // 也可以写 l-1
maxR = Math.max(maxR, right[l]);
}
return -1;
}
}
func findValidSplit(nums []int) int {
left := map[int]int{} // left[p] 表示质数 p 首次出现的下标
right := make([]int, len(nums)) // right[i] 表示左端点为 i 的区间的右端点的最大值
f := func(p, i int) {
if l, ok := left[p]; ok {
right[l] = i // 记录左端点 l 对应的右端点的最大值
} else {
left[p] = i // 第一次遇到质数 p
}
}
for i, x := range nums {
for d := 2; d*d <= x; d++ { // 分解质因数
if x%d == 0 {
f(d, i)
for x /= d; x%d == 0; x /= d {
}
}
}
if x > 1 {
f(x, i)
}
}
maxR := 0
for l, r := range right {
if l > maxR { // 最远可以遇到 maxR
return maxR // 也可以写 l-1
}
maxR = max(maxR, r)
}
return -1
}
func max(a, b int) int { if a < b { return b }; return a }
'''
质因子p,
'''
class Solution:
def findValidSplit(self, nums: List[int]) -> int:
left = {} # left[p] 表示质数 p 首次出现的下标
right = [0] * len(nums) # right[i] 表示左端点为 i 的区间的右端点的最大值
def f(p: int, i: int) -> None:
if p in left:
right[left[p]] = i # 记录左端点 l 对应的右端点的最大值
else:
left[p] = i # 第一次遇到质数 p
for i, x in enumerate(nums):
d = 2
while d * d <= x: # 分解质因数
if x % d == 0:
f(d, i)
x //= d
while x % d == 0:
x //= d
d += 1
if x > 1: f(x, i)
max_r = 0
for l, r in enumerate(right):
if l > max_r: # 最远可以遇到 max_r
return max_r # 也可以写 l-1
max_r = max(max_r, r)
return -1
