qoj10519 萤火虫难题：
https://qoj.ac/problem/10519。
首先不考虑颜色不同的条件，设 \(f_{i,p}\) 表示考虑到第 \(i\) 个数，其中最后一个被选的数有一个质因子是 \(p\) 最多能选多少个数。
转移就是：
\[f_{i,p}\gets f_{i-1, q}+1
\]
其中 \(p,q\) 是 \(w_i\) 的质因子。
滚动数组一下就变成 \(O(n\log n)\) 的了。
https://qoj.ac/problem/10519。
首先不考虑颜色不同的条件，设 \(f_{i,p}\) 表示考虑到第 \(i\) 个数，其中最后一个被选的数有一个质因子是 \(p\) 最多能选多少个数。
转移就是：
其中 \(p,q\) 是 \(w_i\) 的质因子。
滚动数组一下就变成 \(O(n\log n)\) 的了。