又是毕业季2
n/k;
又是毕业季2
一开始很容易想到枚举n个数取k个的所有组合，然后分别用辗转相除法求最大公约数，但是复杂度明显不符合要求，于是必须换一种思路。
我们想到，k个数的公约数含义就是这k个数均含有某个因数，如果我们把所有数的因数全部求出来，发现有k个数均含有某个因数，那么这个数必然是这k个数的公约数。其中找出最大的就是它们的最大公约数。但是要如何高效的做到这点呢？考虑到对于k=1，2……，n都要求出，我们可以这么做：
1、 求出每个因数出现的次数。
2、 对于每个次数记录最大的因数。
算法复杂度o(n*sqrt(inf))。
原文：http://www.cnblogs.com/ZDHYXZ/p/7676959.html