因数求和

本文总阅读量次

利用枚举因数的技巧，求一个数的因数之和，写法如下：

sum = 0;
for(int i = 1; i <= sqrt(n); i++){ //枚举因数1
	if(n % i == 0){
		if(i * i == n) sum += i;
		else sum += i + n / i;  //因数2 = n / i
	}
}

如果要计算因数个数，只要把sum += i改为sum++, sum += i + n / i 改为 sum += 2。

课后习题

1091:因子求和

不包括 $1$ 和本身，所以枚举起点改为 $2$ 即可。

1769:因子个数

模板题，参考因数求和。

3051:约数个数(1)

模板题，参考因数求和。

1771:因子游戏

两个问题：

找出因数个数为 $k$ 的最小数。
从小到大输出最小数的所有因数。

for(int n = 1; n <= 20000; n++){ //从小到大枚举n
	sum = 0;
	for(int i = 1; i <= sqrt(n); i++){ //计算n的因数个数
		...
	}
	if(sum == k){
		cout<<...<<endl; //问题1
		for(int j = 1; j <= n; j++){ //n很小，直接枚举
			if(...) cout<<...;
		}
		
	}
}

别忘记还有找不到的情况。