题目136：考察方程x^2 - y^2 - z^2 = n何时有唯一解

欧拉计划

Singleton difference

The positive integers, x, y, and z, are consecutive terms of an arithmetic progression. Given that n is a positive integer, the equation, x² − y² − z² = n, has exactly one solution when n = 20:

13² − 10² − 7² = 20

In fact there are twenty-five values of n below one hundred for which the equation has a unique solution.

How many values of n less than fifty million have exactly one solution?

题目：

正整数 x，y 和 z 是等差数列中的三个连续项。给定一个正整数 n，当 n=20 时方程 x² − y² − z² = n 有唯一解：

13² − 10² − 7² = 20

事实上，一百以下共有 25 个 n 值使得上述方程有唯一解。

在 5000 万以下有多少个 n 值使得上述方程有唯一解？

jerryxjr1220

本题和135题是一样的，改下参数就好了

1. """
   
2. (z+2d)^2-(z+d)^2-z^2=n
   
3. 3d^2+2dz-z^2=n
   
4. (3d-z)*(d+z)=n
   
5. z<3d => d > z/3
   
6. """
   
7. from numba import jit
   
8. import numpy as np
   
9. @jit
   
10. def solve(target, limit):
    
11.         master = np.zeros(limit+1,dtype='int16')
    
12.         for z in range(1, limit):
    
13.                 for d in range(z//3+1, limit):
    
14.                         if (3*d-z)*(d+z)>limit:
    
15.                                 break
    
16.                         master[(3*d-z)*(d+z)] += 1
    
17.         count = 0
    
18.         for value in master:
    
19.                 if value == target:
    
20.                         count += 1
    
21.         return count
    
22. print(solve(1, 50000000))

复制代码

2544559
[Finished in 4.5s]

guosl

应用OpenACC来编程。

1. /*
   
2. 答案：2544559
   
3. 耗时：2.17018s (cmp 30hx)
   
4. */
   
5. #include <iostream>
   
6. #include <cmath>
   
7. #include <omp.h>
   
8. #include <openacc.h>
   
9. using namespace std;
   
10. 
    
11. int main(void)
    
12. {
    
13.   double t = omp_get_wtime();
    
14.   int nCount = 0;
    
15. #pragma acc kernels loop reduction(+:nCount)
    
16.   for (int n = 1; n <= 50000000; ++n)
    
17.   {
    
18.     int s = -1;//记录所以整数解
    
19.     bool bFlag = false;
    
20.     int d1 = (int)sqrt((double)n);
    
21.     for (int m1 = 1; m1 <= d1; ++m1) //枚举n的因数分解
    
22.     {
    
23.       if (n % m1 == 0)
    
24.       {
    
25.         int m2 = n / m1;
    
26.         if ((m1 + m2) % 4 != 0) //检查d是否是一个整数
    
27.           continue;
    
28.         int d = (m1 + m2) / 4;
    
29.         if (m1 - d > 0)
    
30.         {
    
31.           if (s == -1 || s == (m1 - d))
    
32.           {
    
33.             s = (m1 - d);//得到一个整数解
    
34.             bFlag = true;
    
35.           }
    
36.           else
    
37.           {
    
38.             bFlag = false;
    
39.             break;
    
40.           }
    
41.         }
    
42.         if (m2 - d > 0)
    
43.         {
    
44.           if(s == -1 || s == (m2 - d))
    
45.           {
    
46.             s = (m2 - d);//得到一个整数解
    
47.             bFlag = true;
    
48.           }
    
49.           else
    
50.           {
    
51.             bFlag = false;
    
52.             break;
    
53.           }
    
54.         }
    
55.       }
    
56.     }
    
57.     if (bFlag)//检查解的唯一性
    
58.       ++nCount;
    
59.   }
    
60.   t = omp_get_wtime() - t;
    
61.   cout << nCount << endl << t << endl;
    
62.   return 0;
    
63. }
    

复制代码