\[\frac{\operatorname{lcm}(x,y)}{\gcd(x,y)}=p^2
\]
\[xy=(p\times\gcd(x,y))^2
\]
可以看出 \(x\) 与 \(y\) 有关联等价于 \(xy\) 是完全平方数，也就是说每个质因子出现次数的奇偶性必须相同，而这东西是有传递性的，我们可以把数根据每个质因子出现次数的奇偶性划分成若干个集合，存在某个质因子出现次数不同就归入不同集合，集合内两两均有关联。用出现次数为奇数的质因数之积即可很好地区分不同的集合。
显然经过第一秒同一集合内的数会变得相同，且质因子出现次数只存在奇变偶的情况。对于一个集合，如果其中的数变成了完全平方数，说明集合大小为偶数，接下来也一直会是完全平方数；如果其中的数仍然没有变成完全平方数，说明集合的大小为奇数，接下来也一直不会是完全平方数。显然大小为奇数的集合质因子出现次数的奇偶性均不会改变，集合之间不会发生合并。
于是分 \(w=0\) 和 \(w>0\) 讨论即可。