官方题解：
https://blog.csdn.net/qq_62464995/article/details/127493921

题目大意

给出数组a[i]，将a分成两个数组x和y，使得\(\forall x[i]\% y[j]\)都相等（\(|x|,|y|>0\)）
构造一组\(|y|\)最大的方案

n<=1e5，1<=ai<=1e6

题解

神必结论题

先假设a不是全部相等

结论1：最小值一定只能全在x或y
证明：若最小值min在x和y都有，则模数s=0，发现此时把x的所有min移到y合法且更优
因为s=0，所以如果y里面有大于min的数t，则x的min%y的t=min>s=0，所以y中没有大于min的数
即，所有大于min的数都在x里面，则此时把x中的min移到y之后x不会为空，合法

若最小值全在x，则剩下的数全放到y是合法且最优的（y里面都大于min，x%y=min，全相等），判断掉
接下来考虑最小值全在y的情况：

结论2：设最小值min全在y，若一个数a>min在x，则所有大于a的数b都必须在x
证明：若存在b在y，则y中既有min又有b，a%min<a，a%b=a，矛盾，故b必须在x

根据结论2可以发现，合法的方案就是把原始的a[i]排序后，取前缀丢x、剩下的后缀丢y，枚举所有的前缀情况

由于x和y不能为空，所以a[1]和a[n]一定分别在y和x，所以s=a[n]%a[1]<a[1]

那么得到了s，把所有的x减去s，则变成\(\forall (x[i]-s)\%y[j]=\forall x'[i]\%y[j]=0\)

对x'求gcd，对y求lcm，若gcd%lcm=0则成立，否则不成立
正确性：
\(\forall i,j\)，若gcd%lcm=0，因为x'[i]%gcd=0、lcm%y[j]=0，而gcd%lcm=0，则有x'[i]%y[j]=0，成立；
若gcd%lcm≠0，则存在某个质因子p，gcd中的p的次数a<lcm中的p的次数b
并且一定存在某两个数x'[i0]和y[j0]，使得它们分别贡献了\(p^a\)和\(p^b\)
那么由于\(p^a\%p^b ≠0\)，所以x'[i0]%y[j0]≠0，不成立

所以根据gcd和lcm即可判断所有x'[i]和y[j]的关系，时间O(nlogn)

code

不是我写的