### Solving the diophantine equation 1/a+1/b= p/10n题号：157 难度： 65 中英对照

Consider the diophantine equation 1/a+1/b= p/10n with a, b, p, n positive integers and ab.
For n=1 this equation has 20 solutions that are listed below:

 1/1+1/1=20/10 1/1+1/2=15/10 1/1+1/5=12/10 1/1+1/10=11/10 1/2+1/2=10/10 1/2+1/5=7/10 1/2+1/10=6/10 1/3+1/6=5/10 1/3+1/15=4/10 1/4+1/4=5/10 1/4+1/20=3/10 1/5+1/5=4/10 1/5+1/10=3/10 1/6+1/30=2/10 1/10+1/10=2/10 1/11+1/110=1/10 1/12+1/60=1/10 1/14+1/35=1/10 1/15+1/30=1/10 1/20+1/20=1/10

How many solutions has this equation for 1 ≤ n ≤ 9?

### Code


public final class p157 {
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 LIMIT = 9 + 1;
int result = 0;

int[] sols2 = new int[LIMIT];
sols2[0] = 1;
for (int n = 1; n < LIMIT; n++)
sols2[n] = sols2[n - 1] << 1;

int[] sols5 = new int[LIMIT];
sols5[0] = 1;
for (int n = 1; n < LIMIT; n++)
sols5[n] = sols5[n - 1] * 5;

for (int n = 1; n < LIMIT; n++) {
int ten=1;
for(int i=0;i<n;i++) ten*=10;
for (int ai = 0; ai <= n; ai++) {
for (int bi = 0; bi <= n; bi++) {
result += solveDiophantine(sols2[ai], sols5[bi], ten);
}
}
for (int ai = 1; ai <= n; ai++) {
for (int bi = 1; bi <= n; bi++) {
result += solveDiophantine(1, sols2[ai] * sols5[bi], ten);
}
}
}
return result+"";
}

public static int solveDiophantine(int a, int b, int zehn) {
long sumOfTen = (long) zehn * (a + b);
if (sumOfTen % b != 0 || sumOfTen % a != 0)
return 0;
return get((int) (sumOfTen / (a * b)));
}

public static int get(int n) {
int res = 1;
for (int k = 2; k * k <= n; k++) {
int cnt = 1;
while (n % k == 0) {
n /= k;
cnt++;
}
res*=cnt;
}
if (n != 1)
res<<=1;
return res;
}

}
53490
0ms