Leetcode 2436. Minimum Split Into Subarrays With GCD Greater Than One

Partition an integer array into the minimum number of contiguous subarrays such that each subarray's GCD is greater than 1 (i.e., all elements in a segment share a common prime factor), or report it's impossible. The core challenge is efficiently identifying valid segments (where running GCD stays >1) and using DP/graph/greedy techniques to compute the minimal cuts under typical large-array constraints.