1

私はこの問題を試していました、 http：//www.spoj.pl/problems/TWOSQ/。数（10 ^ 15まで）を二乗和として表現するさまざまな方法の数を見つける必要があります（2回カウントせずに、つまり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

私が見ることができる2つの問題があります。

  1. の計算ではb2、式 を使用しますa*a。が単なる int の場合a、これはすぐにオーバーフローします。
  2. の値EPSが大きすぎます。誤検知が発生します。

倍精度浮動小数点数は、最大 53 有効ビットを使用して格納されます。これは、約 8e15 までのすべての整数を正確に表現できることを意味します。このような数値の平方根を正しく丸めるには、精度を約 2 倍にする必要があるため、範囲内に 4e15 が残ります。

したがって、次の 2 つのことを行います。

  1. すべての変数を double に変更します。
  2. EPS完全に廃止し、正確な比較を使用します。指定した範囲内 (X = 1e15 まで) で問題なく動作するはずです。
于 2012-06-14T05:31:45.953 に答える
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 に答える
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

メイン ループでの 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 に答える