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

Repunit divisibility 题号:129 难度: 45 中英对照

A number consisting entirely of ones is called a repunit. We shall define R(k) to be a repunit of length k; for example, R(6) = 111111.

Given that n is a positive integer and GCD(n, 10) = 1, it can be shown that there always exists a value, k, for which R(k) is divisible by n, and let A(n) be the least such value of k; for example, A(7) = 6 and A(41) = 5.

The least value of n for which A(n) first exceeds ten is 17.

Find the least value of n for which A(n) first exceeds one-million.

Solution

设A(n)=k,那么R(k)%n可通过下面公式计算$$R(k)\%n=(R(k-1)\%n+10^{k-1}\%n)\%n$$对于每一个n,k从1开始递增,直到第一个满足R(k)%n=0时的k即为该n下最小的k值 另外,可被形如111...这样的数,不可能被2和5的倍数整除 因为$$3\times7=21,9\times9=81$$而2和5的倍数和其他任意数的乘积都不可能存在尾数为1的情况

Code

public final class p129 {
	private static final int LIMIT = (int) Math.pow(10, 6);
	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(){
		for (long n = LIMIT; ; n++) {
			if (findLeastDivisibleRepunit(n) > LIMIT)
				return n;
		}
	}
	
	private static int findLeastDivisibleRepunit(long n) {
		if (n % 2 == 0 || n % 5 == 0)
			return 0;
		if (n > Integer.MAX_VALUE / 10)
			throw new IllegalArgumentException("Arithmetic overflow");
		
		long sum = 1;  // 表示R(k) mod n
		long pow = 1;  // 表示10^(k-1) mod n
		int k = 1;
		while (sum % n != 0) {
			k++;
			pow = pow * 10 % n;
			sum = (sum + pow) % n;
		}
		
		return k;
	}
	
}
1000023
114ms