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

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

 1x + 1y = 1n

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.

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