题目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题是一样的，改下参数就好了

"""
(z+2d)^2-(z+d)^2-z^2=n
3d^2+2dz-z^2=n
(3d-z)*(d+z)=n
z<3d => d > z/3
"""
from numba import jit
import numpy as np 
@jit
def solve(target, limit):
        master = np.zeros(limit+1,dtype='int16')
        for z in range(1, limit):
                for d in range(z//3+1, limit):
                        if (3*d-z)*(d+z)>limit:
                                break
                        master[(3*d-z)*(d+z)] += 1
        count = 0
        for value in master:
                if value == target:
                        count += 1
        return count
print(solve(1, 50000000))

2544559
[Finished in 4.5s]

guosl

应用OpenACC来编程。

/*
答案：2544559
耗时：2.17018s (cmp 30hx)
*/
#include <iostream>
#include <cmath>
#include <omp.h>
#include <openacc.h>
using namespace std;

int main(void)
{
  double t = omp_get_wtime();
  int nCount = 0;
#pragma acc kernels loop reduction(+:nCount)
  for (int n = 1; n <= 50000000; ++n)
  {
    int s = -1;//记录所以整数解
    bool bFlag = false;
    int d1 = (int)sqrt((double)n);
    for (int m1 = 1; m1 <= d1; ++m1) //枚举n的因数分解
    {
      if (n % m1 == 0)
      {
        int m2 = n / m1;
        if ((m1 + m2) % 4 != 0) //检查d是否是一个整数
          continue;
        int d = (m1 + m2) / 4;
        if (m1 - d > 0)
        {
          if (s == -1 || s == (m1 - d))
          {
            s = (m1 - d);//得到一个整数解
            bFlag = true;
          }
          else
          {
            bFlag = false;
            break;
          }
        }
        if (m2 - d > 0)
        {
          if(s == -1 || s == (m2 - d))
          {
            s = (m2 - d);//得到一个整数解
            bFlag = true;
          }
          else
          {
            bFlag = false;
            break;
          }
        }
      }
    }
    if (bFlag)//检查解的唯一性
      ++nCount;
  }
  t = omp_get_wtime() - t;
  cout << nCount << endl << t << endl;
  return 0;
}