自动搬运

查看原文

来自洛谷，原作者为

	lzn **

搬运于2025-08-24 21:24:49，当前版本为作者最后更新于2013-07-31 22:41:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

《又是毕业季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))。