题目136：考察方程x^2 - y^2 - z^2 = n何时有唯一解
Singleton differenceThe positive integers, x, y, and z, are consecutive terms of an arithmetic progression. Given that n is a positive integer, the equation, x2 − y2 − z2 = n, has exactly one solution when n = 20:
132 − 102 − 72 = 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 时方程 x2 − y2 − z2 = n 有唯一解：
132 − 102 − 72 = 20
事实上，一百以下共有 25 个 n 值使得上述方程有唯一解。
在 5000 万以下有多少个 n 值使得上述方程有唯一解？ 本题和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
应用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;
}
页:
[1]