算法的優化

Question

這裏是link的問題。

問題詢問到窗體 1/X + 1/Y = 1/Z的不定方程解的數目（其中 Z = N！）。重新排列給定的等式清楚地表明答案是因子的數量 z。

所以問題很容易找到因子 n！。

我的算法如下

1. 進行布爾查找表的所有素數< = N使用埃拉托色尼算法的篩。
2. 迭代所有素數 P < = n並在 n中找到其指數n！。我用step函數公式做了這個。設指數爲 K，則指數爲 P in n！將是 2K。
3. 使用步驟2用標準公式計算因子數量。

對於 N = 10最壞的情況下輸入，我的C代碼給出答案在0.056s。 我想複雜度不會超過 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; 
} 

Answer 1

你有一個int溢出這裏：

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

如果46340 < i < 65536和許多大型i，在第二次迭代j將是負面的，如果溢出時迴繞（這是未定義的行爲，所以任何事情都可能發生）。

用例如，

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

但是，由於它是，不可能的，額外的迭代由於溢出會導致一個「超出時間限制」，這將有可能只會導致錯誤的結果。

所以一般建議是

• 篩只有奇數，或許還可以消除從篩3的倍數。從篩中消除奇數大致減少了篩分所需的時間。
• 不要使用整個int作爲標誌，使用位或至少char s。這樣可以提供更好的緩存局部性和更快的速度。