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

Large repunit factors 题号:132 难度: 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(10) = 1111111111 = 11×41×271×9091, and the sum of these prime factors is 9414.

Find the sum of the first forty prime factors of R(109).

Solution

设$R(k)=\frac{10^k-1}{9}$ 再设$R(k)$的一个素因子是$p$,那么: $$R(k)\equiv 0\quad (mod \quad p)$$ 即为 $$10^k-1 \equiv 0 \quad (mod \quad 9p)$$ 即 $$10^k\equiv 1 \quad (mod\quad 9p)$$ 这样枚举素数$p$,判断$10^k-1$是否能被$9p$整除即可。

Code

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;

public final class p132 {
    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 sum = 0;
		int count = 0;
		for (int i = 2; count < 40; i++) {
			if (isPrime(i) && repunitMod(1000000000, i) == 0) {
				sum += i;
				count++;
			}
		}
		return Integer.toString(sum);
	}
	
    static private boolean isPrime(int i){
    	if(i<=1) return false;
    	if(i==2) return true;
    	if((i&1)==0) return false;
    	for(int j=3;j<=i/j;j++)
    		if(i%j==0) return false;
    	return true;
    }
	
	private static int repunitMod(int k, int m) {
		return (power(10, k, m * 9) - 1) / 9;
	}
	
	static int power(int x,int y,int m){
		int z = 1;
		while (y != 0) {
			if ((y & 1) != 0)
				z = (int)((long)z * x % m);
			x = (int)((long)x * x % m);
			y >>>= 1;
		}
		return z;
	}
}
843296
46ms