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

Number Rotations 题号:168 难度: 65 中英对照

Consider the number 142857. We can right-rotate this number by moving the last digit (7) to the front of it, giving us 714285.
It can be verified that 714285=5×142857.
This demonstrates an unusual property of 142857: it is a divisor of its right-rotation.

Find the last 5 digits of the sum of all integers n, 10 < n < 10100, that have this property.

Solution

考虑一个$p$位的数字$num$,和一位数$a$,则存在整数$n$使得 $$\overline{a\ num}=n\times \overline{num\ a}$$ 即为: $$a\times 10^{p-1}+num=n\times \left( num\times 10 +a \right)$$ 化简为: $$\left( 10^{p-1} -n \right) a=(9n-1)b$$ 显然$n\leq 9$,否则位数会增长。 枚举$p$、$n$和$a$,对上式进行求解和判定即可。

Code

import java.math.BigInteger;

public final class p168 {
    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" );
    }

	private static final BigInteger TEN = BigInteger.valueOf(10);
	
    static public String run() {
    	BigInteger sum=BigInteger.ZERO;
		for (int pow = 1; pow < 101; pow++) {
			for (BigInteger a = BigInteger.ONE; a.compareTo(TEN) < 0; a = a
					.add(BigInteger.ONE)) {
				for (BigInteger n = BigInteger.ONE; n.compareTo(TEN) < 0; n = n
						.add(BigInteger.ONE)) {
					final BigInteger denom = ((TEN.pow(pow)).subtract(n))
							.multiply(a);
					final BigInteger div = (TEN.multiply(n))
							.subtract(BigInteger.ONE);

					if (denom.mod(div).equals(BigInteger.ZERO)) {
						final BigInteger num = denom.divide(div);
						if (num.toString().length() == pow) {
							final BigInteger value = new BigInteger("" + num
									+ a);
							if (value.toString().length() <= 100) {
								sum = sum.add(value);
							}
						}
					}
				}
			}
		}
		return sum.mod(BigInteger.valueOf(100000)).toString();
	}
}
59206
101ms