アルゴリズムの最適化

Question

ここにはの問題があります。

問題がフォーム 1/X + 1/Y = 1/Z（ Z = N！）のディオファントス方程式の解の数を尋ねます。与えられた方程式を再整理すると、答えは因子数が zであることが明らかです。

問題は、要因の数が nです。。

私のアルゴリズムは

1. を次のようにすべての素数<のブールルックアップテーブルを作成している= Nエラトステネスアルゴリズムのふるいを使用して。全ての素数を超える
2. 反復 P < = Nと nは、指数を見つけて下さい！。私はステップ関数式を使ってこれを行いました。指数を Kとし、次に指数 Pを n！とします。は、 2Kとなります。
3. 手順2を使用して、標準式で係数の数を計算します。

の最悪の場合の入力について

N = 10、私のCコードは、0.056sで答えを与えます。 私は複雑さが O（ng 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; 
} 

Answer 1

現在地intオーバーフローがあります。オーバーフローがラップアラウンドする場合

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

46340 < i < 65536の場合と2回目の反復jで、i大きな多くはマイナスになるために（それは未定義の動作なので、何かが起こる可能性があります）。

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

原因オーバーフローへの余分な反復がおそらく唯一の誤った結果を引き起こします「超過時間制限」を、引き起こすこと、しかし、ほとんどありません。

ので、一般的なアドバイスが

• ふるい奇数のみであるが、おそらくもふるいから3の倍数を排除します。篩から奇数を取り除くことは、ふるい分けに必要な時間をおよそ半分にします。
• フラグ、使用ビット、または少なくともcharにはintを使用しないでください。これにより、キャッシュの局所性が向上し、さらに高速化されます。