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

Diophantine reciprocals II 题号:110 难度: 40 中英对照

In the following equation x, y, and n are positive integers.

1
x
+
1
y
=
1
n

It can be verified that when n = 1260 there are 113 distinct solutions and this is the least value of n for which the total number of distinct solutions exceeds one hundred.

What is the least value of n for which the number of distinct solutions exceeds four million?

NOTE: This problem is a much more difficult version of Problem 108 and as it is well beyond the limitations of a brute force approach it requires a clever implementation.

Solution

请先参考问题108,其推导过程一致。对于本题: 首先,前15个素数的乘积是本题答案的一个上界,因为$(2\times 1+1)^{15}>8000000$。 其次,需要从大到小把这15个素数依次扔掉,当扔掉素数p时,应在$[2,p-1]$之间选取一个数q,来把p替换为q。 此时把q质因数分解,它只包含小于p的所有素数的因子,记这个因式分解式为qr。 我们枚举q,将q替代p,并计算替代后的N和S($N=\prod_i^n p_i^{r_i},\quad S=\prod_i^n (2r_i+1)$),要使得S大于8000000,且N尽可能小。 如果找不到比当前更小的N,则不继续替换。

Code


public final class p110 {
    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(){
    	long ans=Long.MAX_VALUE;
    	int r[]=new int[15];
    	for(int i=0;i<15;i++) r[i]=1;
    	for(int cnt=15;cnt>=1;cnt--){
    		//当前扔掉prime[cnt-1],剩下cnt-1个素因子
    		long min=ans;
    		int Q=0,Qr[]=new int[cnt-1];
    		for(int q=2;q<prime[cnt-1];q++){
    			int qr[]=new int[cnt-1];
    			for(int i=0;i<qr.length;i++) qr[i]=0;
    			int tmp=q;
    			for(int i=0;i<qr.length;i++){
   					while(tmp%prime[i]==0){
   						qr[i]++;
   						tmp/=prime[i];
    				}
    			}
    			long N=1;
    			long S=1;
    			for(int i=0;i<qr.length;i++){
    				N*=pow(prime[i],qr[i]+r[i]);
    				S*=(qr[i]+r[i])*2+1;
    			}
    			if(S>=8000000 && N<min){
    				min=N;
    				Q=q;
    				Qr=qr.clone();
    			}
    		}
    		if(Q==0) break;
    		for(int i=0;i<cnt-1;i++)
    			r[i]+=Qr[i];
    		r[cnt-1]=0;
    		if(min<ans) ans=min; 
    	}
    	return Long.toString(ans);
    }

    static public final int prime[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};
    static public long pow(long a,int n){
    	long res=1;
    	while(n-->0) res*=a;
    	return res;
    }
    
    
}
9350130049860600
1ms