题解 P1414 【又是毕业季II】
《又是毕业季II》解题报告
By lzn 数论常规题。
一开始很容易想到枚举n个数取k个的所有组合，然后分别用辗转相除法求最大公约数，但是复杂度明显不符合要求，于是必须换一种思路。
我们想到，k个数的公约数含义就是这k个数均含有某个因数，如果我们把所有数的因数全部求出来，发现有k个数均含有某个因数，那么这个数必然是这k个数的公约数。其中找出最大的就是它们的最大公约数。但是要如何高效的做到这点呢？考虑到对于k=1，2……，n都要求出，我们可以这么做：
* 1、 求出每个因数出现的次数。
* 2、 对于每个次数记录最大的因数。
* 3、 根据f[k]=max(f[k],f[k+1])逆向递推。（如果已经知道k个数的最大公约数是m，那么l(l<k)个数的最大公约数一定大于等于m）。
具体为什么这么做，留给大家自己思考啦~~
算法复杂度o(n*sqrt(inf))。