约数-求一个数的约数、约数个数、约数之和

1、求一个数的约数

vector<int> get_divisors(int x){
	vector<int> ve;
	for(int i = 1; i * i <= x; ++i){
		if(x % i == 0){
			x /= i;
			ve.push_back(i);
			if(i != x / i)
				ve.push_back(x / i);
		}
	}
	return ve;
}

2、约数个数

我们知道一个数
X = (p1^a1) * (p2^a2) * (p3^a3) * (p4^a4) * . . . * (pn^an)，其中pi是质数，ai是相应的个数，
那么约数个数=(a1+1)*(a2+1） * . . . * (an+1)。

int get_divisors_num(int x){
	int sum = 1;
	for(int i = 2; i * i <= x; ++i){
		int cnt = 1;
		if(x % i == 0){
			while(x % i == 0){
				cnt++;
				x /= i;
			}
			sum *= cnt;
		}
	}
	// 还有大于根号x的约数
	if(x > 1) sum *= 2;
	return sum;
}

3、约数和

约数和其实可以从约数个数看出来，相当于从
(p1^0 + p1^1 + . . . + p1^a1) * . . . * (pn^0 + . . . + pn^an)中每一项中挑选一个元素，然后相乘组成一个约数，累加起来就是约数和。

typedef long long LL;
const int mod = 1e9 + 7;
LL get_divisors_sum(int x){
	LL sum = 1;
	for(int i = 2; i * i <= x; ++i){
		LL temp = 1;
		if(x % i == 0){
			LL j = i;
			while(x % i == 0){
				temp += j;
				j *= i;
				x /= i;
			}
			sum = (sum * temp) % mod;
		}
	}
	// 最后一个约数x>1，那么乘上(x^0 + x^1)
	if(x > 1) sum = (sum * (1 + x)) % mod;
	return sum;
}