1

我正在尝试这个问题， http://www.spoj.pl/problems/TWOSQ/。我们必须找到将数字（大至 10^15）表示为平方和的不同方式的数量（不计算两次，即 5^2 + 1^2 和 1^2 + 5^2 是相同的） . 我以前见过这个任务，这也是我之前解决它的方法。我一直在法官那里得到错误的答案。有人能告诉我为什么吗？或完全提出不同的方法。我已经添加了必要的评论以便理解。提前致谢！。

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;

int main()
{
long long X;
cin >> X;
const double EPS = 1e-6;
long long int count = 0;
// add EPS to avoid flooring x.99999 to x
for (int a = 0; a <= sqrt(X/2) + EPS; a++)
{
    long long int b2 = X - a*a; // b^2
    long long int b = (long long int) (sqrt(b2) + EPS);
    if (abs(b - sqrt(b2)) < EPS) // check b is an integer
        count++;
}
cout << count << endl;

}

4

4 回答 4

1

我可以看到两个问题。

  1. 在计算 时b2，您使用表达式a*a。如果a只是一个 int，那么这将很快溢出。
  2. 你的价值EPS太大了。你会得到误报。

双精度浮点数最多使用 53 个有效位进行存储。这意味着可以精确表示高达约 8e15 的所有整数。要正确舍入此类数字的平方根，您需要将精度提高一倍左右，这样您的 4e15 仍然在您的范围内。

所以，我会做两件事：

  1. 将我所有的变量更改为双精度数。
  2. 完全取消EPS并使用精确的比较。它们应该在您指定的范围内正常工作（最多 X = 1e15）。
于 2012-06-14T05:31:45.953 回答
0

您在主循环中使用 EPS 存在根本缺陷（可以想象，由于丢番图的原因，它可以避免任何实际错误，但这需要更多的思考而不是保证）。假设 X/2 非常接近完美正方形，例如 10^14-1。那么 sqrt(X/2) 将约为 10^7 - 0.5*10^-7，这将下溢双精度浮点数并舍入到 10^7。

为什么不在 2*a*a > X 时停止循环？当然，修复你的整数溢出危险。

于 2012-06-14T04:45:48.317 回答
0

我想我知道您要做什么，这很酷……试试这个：

#include<cstdio>
#include<iostream>
#include<cmath>

using namespace std;

typedef unsigned long long int data_type;

int main()
{
    data_type value = 0,
              count = 0, 
              index = 0, 
              max = 0,         
              b_1 = 0; 

    cin >> value;
    max = (data_type)sqrt(value);
    char *flags = new char[max];
    memset(flags, 0, max);

    for (index = 0; index < max; index++)
    {   
        b_1 = value - (index * index);        

        if (!((data_type)sqrt(b_1) - sqrt(b_1)) && !flags[(data_type)(sqrt(b_1))] && !flags[index])
        {
            flags[(data_type)sqrt(b_1)] = 1;
            flags[index] = 1;
            count++;                          
        }
    }        

    cout << count << endl;
}

据我所知，平方然后取差，通过取平方根并检查任何剩余浮点值来检查该差本身是否是一个完美的平方，有点酷。

这还没有经过彻底测试因此，如果有任何错误或问题，我深表歉意。

正如我认为它的好把戏，问题是重复。

请注意，这(10**15)**.5大约是 32 兆，所以这就是分配
好运的数量。

于 2012-06-14T05:21:45.707 回答
0

我尝试了很多，但由于某种原因仍然得到错误的答案。因此，我研究了一种不同的方法，并能够找出这个非常快速的解决方案。

 long long L=res=0, R=(long long)sqrt(X) + 1;     
while (L<=R)
{
    long long Y = L*L + R*R;
    if (Y > X) R--;
    else if (Y < X) L++;
    else res++, L++;
}
于 2012-06-15T01:18:05.457 回答