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

Digital root sums of factorisations 题号:159 难度: 60 中英对照

Digital root sums of factorisations

A composite number can be factored many different ways. For instance, not including multiplication by one, 24 can be factored in 7 distinct ways:

24 = 2x2x2x3
24 = 2x3x4
24 = 2x2x6
24 = 4x6
24 = 3x8
24 = 2x12
24 = 24

Recall that the digital root of a number, in base 10, is found by adding together the digits of that number, and repeating that process until a number is arrived at that is less than 10. Thus the digital root of 467 is 8.

We shall call a Digital Root Sum (DRS) the sum of the digital roots of the individual factors of our number.
The chart below demonstrates all of the DRS values for 24.

Factorisation Digital Root Sum
2x2x2x3 9
2x3x4 9
2x2x6 10
4x6 10
3x8 11
2x12 5
24 6

The maximum Digital Root Sum of 24 is 11.
The function mdrs(n) gives the maximum Digital Root Sum of n. So mdrs(24)=11.
Find ∑mdrs(n) for 1 < n < 1,000,000.


分解约数数字根之和

每个合数都有很多种分解约数的方式。例如,如果不允许多次乘1,有7种不同的方式分解24的约数:

24 = 2x2x2x3
24 = 2x3x4
24 = 2x2x6
24 = 4x6
24 = 3x8
24 = 2x12
24 = 24

在十进制下,一个数的数字根是不断重复将其各位数字相加,直到得到的结果小于10为止。因此467的数字根是8。

我们记数字根和(DRS)是所有分解出的约数的数字根之和。
下表是24的所有约数分解的DRS值。

约数分解 数字根和
2x2x2x3 9
2x3x4 9
2x2x6 10
4x6 10
3x8 11
2x12 5
24 6

对于24的所有分解,最大的数字根和是11。
函数mdrs(n)表示对于n的不同分解最大的数字根和。因此mdrs(24)=11。
对于1 < n < 1,000,000,求∑mdrs(n)。


Solution

考虑任何一个$n$,一个明显的$drs(n)$值是他自身的数字根,而$n$的数字根恰好等于$mod(n-1,9)+1$(这是显然的)。 对于$n$,如果$a\times b=n$,且$a,b$满足$a!=1,a< b$,则 $$mdrs(n)=mdrs(a\times b)=max\left[ mdrs(a),mdrs(b) , mdrs_{now}[n] \right]$$ 其中$mdrs_{now}[n]$表示目前已知的最大$drs(n)$。 于是只需要不断枚举$a$和$b$,更新$mdrs[a\times b]$即可。

Code

public final class p159 {
    public static void main(String[] args) {
        long start=System.nanoTime();
        String result = run();        
        long end=System.nanoTime();
        System.out.println(result);
        System.out.println( (end-start)/1000000 + "ms" );
    }
    static public String run() {
		int[] X = new int[1000000];
		int sum = 0;
		for (int i = 2; i < X.length; i++)
			X[i] = (i - 1) % 9 + 1;
		for (int j = 2; j < 1000000; j++) {
			int drsj = X[j];
			for (int k = 2, n = j + j; k <= j && n < 1000000; k++, n += j)
				X[n] = Math.max(X[n], drsj + X[k]);
			sum += drsj;
		}
		return sum+"";
	}

}
14489159
107ms