题目157：7求解丢番图方程1/a+1/b= p/10^n

欧拉计划

Solving the diophantine equation ¹/_a+¹/_b= ^p/₁₀n

Consider the diophantine equation ¹/_a+¹/_b= ^p/₁₀n with a, b, p, n positive integers and a ≤ b.

For n=1 this equation has 20 solutions that are listed below:



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

题目：

考虑丢番图方程 ¹/_a+¹/_b= ^p/₁₀n ，a, b, p, n 都是正数，并且 a ≤ b

对于 n=1，则该方程有下面二十个解：

¹/₁+1/1=²⁰/₁₀            ¹/₁+¹/₂=¹⁵/₁₀           ¹/₁+¹/₅=¹²/₁₀            ¹/₁+¹/₁₀=¹¹/₁₀            ¹/₂+¹/₂=¹⁰/₁₀
¹/₂+¹/₅=⁷/₁₀              ¹/₂+¹/₁₀=⁶/₁₀            ¹/₃+¹/₆=⁵/₁₀            ¹/₃+¹/₁₅=⁴/₁₀              ¹/₄+¹/₄=⁵/₁₀
¹/₄+¹/₂₀=³/₁₀             ¹/₅+¹/₅=⁴/₁₀           ¹/₅+¹/₁₀=³/₁₀            ¹/₆+¹/₃₀=²/₁₀              ¹/₁₀+¹/₁₀=²/₁₀
¹/₁₁+¹/₁₁₀=¹/₁₀         ¹/₁₂+¹/₆₀=¹/₁₀          ¹/₁₄+¹/₃₅=¹/₁₀          ¹/₁₅+¹/₃₀=¹/₁₀          ¹/₂₀+¹/₂₀=¹/₁₀

请问，对于 1 ≤ n ≤ 9，该方程有多少个解？

guosl

先将p设为1，则原方程化为1/a + 1/b = 1/10^n。令m=10^n,a=m+x，b=m+y。则方程可以化为xy=m^2。对m^2进行因数分解可以求解，如果a,b有公因数p>1，则这个解可以化成1/a+1/b=p/10^n的解。

1. /*
   
2. 答案：53490
   
3. */
   
4. #include <iostream>
   
5. #include <cmath>
   
6. using namespace std;
   
7. 
   
8. const int N = 9;
   
9. 
   
10. unsigned long long mpow(int n, int m)
    
11. {
    
12.   unsigned long long p = 1;
    
13.   for (int i = 0; i < n; ++i)
    
14.     p *= 2;
    
15.   for (int i = 0; i < m; ++i)
    
16.     p *= 5;
    
17.   return p;
    
18. }
    
19. 
    
20. unsigned long long gcd(unsigned long long x, unsigned long long y)
    
21. {
    
22.   if (y == 0)
    
23.     return x;
    
24.   unsigned long long z = x % y;
    
25.   while (z != 0)
    
26.   {
    
27.     x = y;
    
28.     y = z;
    
29.     z = x % y;
    
30.   }
    
31.   return y;
    
32. }
    
33. 
    
34. unsigned long long getmp(unsigned long long k)
    
35. {
    
36.   if ((k % 2) == 0)
    
37.     return 2;
    
38.   unsigned long long u = (unsigned long long)sqrt((double)k);
    
39.   for (unsigned long long i = 3; i <= u; i += 2)
    
40.   {
    
41.     if (k % i == 0)
    
42.       return i;
    
43.   }
    
44.   return k;
    
45. }
    
46. 
    
47. int getdc(unsigned long long d)
    
48. {
    
49.   int nC = 1;
    
50.   while (d != 1)
    
51.   {
    
52.     unsigned long long p = getmp(d);
    
53.     int k = 0;
    
54.     while (d % p == 0)
    
55.     {
    
56.       ++k;
    
57.       d /= p;
    
58.     }
    
59.     nC *= k + 1;
    
60.   }
    
61.   return nC;
    
62. }
    
63. 
    
64. int main(void)
    
65. {
    
66.   int nCount = 0;
    
67.   unsigned long long M = 1;
    
68.   for (int n = 1; n <= N; ++n)
    
69.   {
    
70.     M *= 10;
    
71.     for (int i = 0; i <= 2 * n; ++i)
    
72.     {
    
73.       unsigned long long K1 = mpow(i, 0);
    
74.       if (K1 > M)
    
75.         break;
    
76.       for (int j = 0; j <= 2 * n; ++j)
    
77.       {
    
78.         unsigned long long K2 = K1 * mpow(0, j);
    
79.         if (K2 > M)
    
80.           break;
    
81.         unsigned long long a = M + K2, b = M + mpow(2 * n - i, 2 * n - j);
    
82.         unsigned long long d = gcd(a, b);
    
83.         nCount += getdc(d);
    
84.       }
    
85.     }
    
86.   }
    
87.   cout << nCount << endl;
    
88.   return 0;
    
89. }
    

复制代码