CF 1497E2 - Square-Free Division (hard version)

Rating: 2500
Tags: data structures, dp, greedy, math, number theory, two pointers
Solve time: 2m 36s
Verified: no

Solution

Problem Understanding

We are given an array of positive integers, and we are asked to split it into the fewest possible contiguous segments such that within any segment, no pair of numbers multiplies to a perfect square. Additionally, before splitting, we can modify up to $k$ elements to any positive integer to reduce conflicts. The goal is to minimize the number of segments after making at most $k$ changes.

The first observation is that the primary constraint comes from products forming perfect squares. Two numbers multiply to a perfect square if and only if, when you factorize both numbers and consider their prime exponents modulo 2, the exponents sum to an even vector for each prime. This suggests that we can normalize each number by removing squares of primes from its factorization. For example, 18 has a factorization $2^1 \cdot 3^2$, which we can reduce modulo 2 to $2^1 \cdot 3^0 = 2$. Once normalized this way, any two numbers are incompatible if they are equal aft