当前位置:首页 » Project Euler » 详细页

Amicable chains 题号:95 难度: 30 中英对照

The proper divisors of a number are all the divisors excluding the number itself. For example, the proper divisors of 28 are 1, 2, 4, 7, and 14. As the sum of these divisors is equal to 28, we call it a perfect number.

Interestingly the sum of the proper divisors of 220 is 284 and the sum of the proper divisors of 284 is 220, forming a chain of two numbers. For this reason, 220 and 284 are called an amicable pair.

Perhaps less well known are longer chains. For example, starting with 12496, we form a chain of five numbers:

12496 → 14288 → 15472 → 14536 → 14264 (→ 12496 → ...)

Since this chain returns to its starting point, it is called an amicable chain.

Find the smallest member of the longest amicable chain with no element exceeding one million.

Solution

题意是:设数i的因子和为next1,next1的因子和为next2……nextn的因子和为i,组成一条链,求该链中所有数均小于一百万时,n最大情况下的i 求解分为两步,为方便表述,设$$LIMIT=10^{6}$$ - 求[0,LIMIT]中所有数的因子和divisorSum[i],思路是将所有2的倍数的因子和加2,将所有3的倍数的因子和加3…… - 计算n最大时的i 对于[0,LIMIT]的每个数i,n初始为1,cur初始为i$$next=divisorSum[cur]$$$$cur=next$$ 直到next==i或者next已经超出范围LIMIT又或者next已经在该链中出现过时,跳出循环,计算i+1 对于next==i的情况下,如果maxChainLen < n时,最长链长maxChainLen=n,链中的最小数minChainElem=i,则跳出循环,计算i+1 否则如果next已经大于LIMIT或是next已经出现在链中,则跳出循环,计算i+1

Code

public final class p95 {
	private static final int LIMIT=(int)Math.pow(10, 6);
	//private static final int LIMIT=16000;
	public static void main(String[] args){
		long start=System.nanoTime();
        long result = run();        
        long end=System.nanoTime();
        System.out.println(result);
        System.out.println( (end-start)/1000000 + "ms" );
	}
	public static long run(){
		int[] divisorSum = new int[LIMIT + 1];	//divisorSum[n]用来计算n的所有因子之和
		for (int i = 1; i <= LIMIT; i++) {
			for (int j = i * 2; j <= LIMIT; j += i)
				divisorSum[j] += i;
		}
		int maxChainLen = 0;
		long minChainElem = -1;
		for (int i = 0; i <= LIMIT; i++) {
			Set<Integer> visited = new HashSet<>();	//set中元素不可以重复
			int cur=i;
			for (int count = 1; ; count++) {
				visited.add(cur);
				int next = divisorSum[cur];
				
				if (next == i) {
					if (count > maxChainLen) {
						minChainElem = i;
						maxChainLen = count;
					}
					
					break;
				}
				else if (next > LIMIT || visited.contains(next))
					break;
				else
					cur = next;
			}
		}
		return minChainElem;
	}
	
	
}
14316
1318ms