2.约数
根据分摊分析,当数据最够多时,每个数的约数平均为logn个。
(第一个数是n个数的约数 , 第二个数是n/2个数的约数 , 以此类推第n个数是n/n个数的约数。
累加得n(1/1+1/2+1/3+…+1/n)=n(lnn+c)≈nlogn)
(1)试除法O(sqrt(n))
思路:从小到大枚举较小的约数即可
vector<int> get_divisors(int x)
{
vector<int> res;
for(int i = 1 ; i <= x / i ; i++)
{
if(x % i == 0)
{
res.push_back(i);
if(i != x / i) res.push_back(x / i); //特判边界
}
}
sort(res.begin() , res.end());
return res;
}