2

ここに問題へのリンクがあります。

この問題は、 1/x + 1/y = 1/z ( z = n! )の形式のディオファントス方程式の解の数を求めます。与えられた方程式を並べ替えると、答えがz 2の因数の数であることが明確にわかります。

したがって、問題はnの因数の数を見つけることに要約されます。2 ( n階乗の二乗)。

私のアルゴリズムは次のとおりです

  1. エラトステネスのふるいアルゴリズムを使用して、すべての素数 <= n のブール ルックアップ テーブルを作成します。
  2. すべての素数P <= nを反復処理し、nの指数を見つけます! . ステップ関数式を使用してこれを行いました。指数をKとすると、 Pの指数はnです! 2は2Kになります。
  3. ステップ 2 を使用して、標準式で因子の数を計算します。

n = 10 6の最悪の場合の入力に対して、私の C コードは 0.056 秒で答えを出します。複雑さはO(n lg n)よりも大きくないと思います。しかし、サイトにコードを提出したところ、制限時間を超えたため、3/15 のテスト ケースしか合格できず、残りは判定されました。

このアルゴリズムを最適化するためのヒントが必要です。

これまでのコード:

#include <stdio.h>
#include <string.h>

#define ULL unsigned long long int
#define MAXN 1000010
#define MOD 1000007

int isPrime[MAXN];

ULL solve(int N) {
    int i, j, f;
    ULL res = 1;
    memset(isPrime, 1, MAXN * sizeof(int));
    isPrime[0] = isPrime[1] = 0;
    for (i = 2; i * i <= N; ++i)
        if (isPrime[i])
            for (j = i * i; j <= N; j += i)
                isPrime[j] = 0;
    for (i = 2; i <= N; ++i) {
        if (isPrime[i]) {
            for (j = i, f = 0; j <= N; j *= i)
                f += N / j;
            f = ((f << 1) + 1) % MOD;
            res = (res * f) % MOD;
        }
    }
    return res % MOD;
}

int main() {
    int N;
    scanf("%d", &N);
    printf("%llu\n", solve(N));
    return 0;
}
4

1 に答える 1

1

ここにintオーバーフローがあります：

for (j = i, f = 0; j <= N; j *= i)

46340 < i < 65536多くの場合、オーバーフローがラップアラウンドするとi、2回目の反復jで負になります（これは未定義の動作であるため、何かが発生する可能性があります）。

たとえばに置き換えます

for(j = N / i, f = 0; j > 0; j /= i) {
    f += j;
}

ただし、オーバーフローによる余分な反復によって「制限時間超過」が発生する可能性は低く、誤った結果が発生する可能性があります。

したがって、一般的なアドバイスは

  • 奇数のみをふるいにかけ、おそらくふるいから3の倍数を削除します。ふるいから奇数を取り除くと、ふるいに必要な時間が約半分になります。
  • フラグに全体を使用しないでください。intビットまたは少なくともcharsを使用してください。これにより、キャッシュの局所性が向上し、さらに高速化されます。
于 2012-04-16T20:02:46.730 に答える