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

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?

Solution

所有的解都可以由下两式生成: $$\frac{1}{1}+\frac{1}{2^a5^b}=\frac{p}{10^n}$$ $$\frac{1}{2^a}+\frac{1}{5^b}=\frac{p}{10^n}$$ 当$p$有因子$q$时, $$\frac{1}{1}+\frac{1}{2^{q\times a}5^{q\times b}}=\frac{\frac{p}{q}}{10^n}$$ $$\frac{1}{2^{q\times a}}+\frac{1}{5^{q\times b}}=\frac{\frac{p}{q}}{10^n}$$ 也是方程的合法解。 于是分别考虑第一式和第二式,枚举$a,b$,判断$p=\frac{(a+b)10^n}{ab}$是否为整数,若不是则对答案的贡献为0,否则对答案贡献$p$的因子个数。 要注意第一式和第二式当$a=b=0$时是重复的。

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