1.cf D.Strange Definition

https://codeforces.com/contest/1471/problem/D

大意：定义“相邻”，如果两个数x,y。lcm(x,y)/gcd(x,y)是完全平方数，则x,y为相互相邻。T组测试样例

给出一个长度为 n 的数列，每过一秒钟，数列中的每一个元素会被与它相邻的所有元素的乘积（包括它自身）所替换。给出 q 个询问，问在第w秒时，当前数列中哪个元素有最多的相邻元素，不需要给出这个元素是谁，只要给出它的相邻元素个数。

思路：一想到完全平方数，完全平方数的本质：所有质因数的次方是偶数，这是关键，之前也遇到过一道有关完全平方数的题，也是从质因数下手。

首先来看下lcm(x,y)/gcd(x,y)很容易看出是可以化简的，记gd=gcd(x,y),则lcm(x,y)=x*y/gd,所以原式可化为

x*y/(gd^2)=z2。即 x *y=gd^2 *z^2,即 x *y是完全平方数。可以证明x *y为完全平方数和“相邻”是充要条件。

接下来就是看x*y，什么时候是完全平方数，一个一个看肯定是不行的。我们想到，如果x *y是完全平方数，则必须满足x和y的对应的质因数次方奇偶性应一致（0次方看成偶数），这样才能保证x *y对应次方相加，次方是偶数。因为我们关注的是奇偶，所以可以直接将次方模2，次方就只有0和1了。然后通过hash，把质因数奇偶性一致的分到一组，这样这一组的任意两个数都能合成完全平方数。接下来再看随着时间是怎么变的。

如果某组中有偶数个，因为把更新某一个数是把一组中所有的数相乘，偶数个1相加还是偶数，则变成了次方为0的情况（hash值为0），如果某组中有奇数个，那么奇数个1相加还是奇数，模2还是1，等于没变化。因此就0秒和1秒两种情况。完毕。

总结：完全平方数从质因数的次方角度考虑。