### 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.

### 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