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

Composites with prime repunit property 题号:130 难度: 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.

You are given that for all primes, p > 5, that p − 1 is divisible by A(p). For example, when p = 41, A(41) = 5, and 40 is divisible by 5.

However, there are rare composite values for which this is also true; the first five examples being 91, 259, 451, 481, and 703.

Find the sum of the first twenty-five composite values of n for which
GCD(n, 10) = 1 and n − 1 is divisible by A(n).

Solution

- 设A(n)=k,那么R(k)%n,如何求满足条件的最小的k值 方法如下: 可通过下面公式计算$$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的情况 - 求满足5 < i < 25,GCD(i,10)==1,(n-1)%k==0这三个条件的i之和

Code

public final class p130 {
	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(){
		long sum = 0;
		int found = 0;
		for (int i = 7; found < 25; i += 2) {	//因为题设要求i>5,并且2和5的倍数和其他任意数的乘积都不可能存在尾数为1的情况,所以是i+=2
			if (i % 5 != 0 && !isPrime(i) && (i - 1) % findLeastDivisibleRepunit(i) == 0) {
				sum += i;
				found++;
			}
		}
		return sum;
	}
	public static boolean isPrime(int x) {
		if (x < 0)
			throw new IllegalArgumentException("Negative number");
		if (x == 0 || x == 1)
			return false;
		else if (x == 2)
			return true;
		else {
			if (x % 2 == 0)
				return false;
			for (int i = 3, end = (int)Math.sqrt(x); i <= end; i += 2) {
				if (x % i == 0)
					return false;
			}
			return true;
		}
	}
	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;
	}
	
}
149253
390ms