projecteuler21-莫比乌斯求约数和

2017-08-03

Problem 21

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.

这里的d(n)表示n的所有约数和减去自身
$$
d(n) = \sum_{d=1}^{n}{d}-n
$$

这里将f(n)理解为所有的约数和，那么f(n) = d(n)+n , 最后d(n)做一个减法处理

简单的暴力方法肯定没有问题，思考一个问题，在O(n)线性时间复杂度利用莫比乌斯反演的思想利用积性函数来解决。

对于比如24来说：

24 = 2^3 * 3

那么f(24) = f(3)*2^3 + f(12)

因为是利用莫比乌斯反演思想，所以考虑最小的质因子是2的情况下，除去这个因子2，那么还有12中的约数和，那么我们需要确保剩下获取到的约数均和12没有任何关系，而且需要把这个最下的因子2带进去，本身12里面就有两个2的因子，那么也就是说，剩余的约数都是包含三个所有的2，所以对应过来就是f(3)*8

所以我们需要在积性函数构造过程中构造f函数和一个辅助的a函数

f(n)表示n所有的约数和

a(n)表示n最小的质因子的最高幂次

比如24对应了2^3=8—>a(24) = 8,

45 = 3^2*5 —>a(45) = 9


bool vis[10005];
int pri[10005] , tot=0;
int a[10005]; //表示除去最小素数因子剩下的数
int f[10005] , d[10005];
void init(int n)
{
	memset(vis , 0 , sizeof(n+1));
	f[1] = 1 , a[1] = 1;
	for(int i=2 ; i<=n ; i++){
		if(!vis[i]){
			pri[tot++] = i;
			vis[i] = true;
			a[i] = i;
			f[i] = 1+i;
		}
		for(int j=0 ; j<tot ; j++){
			if(pri[j]*i>n) break;
			vis[pri[j]*i] = true;
			if(i % pri[j] == 0){
				a[i*pri[j]] = a[i]*pri[j];
				f[i*pri[j]] = a[i*pri[j]]*f[i*pri[j] / a[i*pri[j]]]+f[i];
				break;
			}
			else{
				a[i*pri[j]] = pri[j];
				f[i*pri[j]] = a[i*pri[j]]*f[i*pri[j] / a[i*pri[j]]]+f[i];
			}
		}
		//printf("%d %d %d\n" , i , a[i] , f[i]);
	}
}
int main()
{
	init(10000);
	int ret = 0;
	
	for(int i=1 ; i<=10000 ; i++) d[i] = f[i] - i;
	cout<<f[220]<<" "<<f[284]<<endl;
	for(int i=1 ; i<=10000 ; i++){
		if(d[i]>10000) continue;
		if(i == d[d[i]]){
			if(i!=d[i]) ret+=i;
			printf("%d %d\n" , i,d[i]);
		}
	}
	printf("%d\n",ret);
	return 0;
}