算法优化[关闭]

这里是link https://www.interviewstreet.com/challenges/dashboard/#problem/4e14a0058572a到问题。

The problem asks the number of solutions to the Diophantine equation of the form 1/x + 1/y = 1/z (where z = n!). Rearranging the given equation clearly tells that the answer is the number of factors of z².

So the problem boils down to finding the number of factors of n!² (n factorial squared).

我的算法如下

1. 使用埃拉托斯特尼筛法算法为所有
2. Iterate over all primes P <= n and find its exponent in n!. I did this using step function formula. Let the exponent be K, then the exponent of P in n!² will be 2K.
3. 使用步骤 2 使用标准公式计算因子数。

For the worst case input of n = 10⁶, my c code gives answer in 0.056s. I guess the complexity is no way greater than O(n lg n). But when I submitted the code on the site, I could pass only 3/15 test cases with the verdict on the rest as time limit exceeded.

我需要一些优化该算法的提示。

到目前为止的代码：

#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;
}

你有一个int此处溢出：

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

If 46340 < i < 65536对于许多较大的i，在第二次迭代中j如果溢出回绕，将为负数（这是未定义的行为，所以任何事情都可能发生）。

将其替换为例如

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

然而，由于溢出而导致的额外迭代不太可能导致“超出时间限制”，这可能只会导致错误的结果。

所以一般建议是

• 只筛奇数，也许也从筛子中消除 3 的倍数。从筛子中消除奇数可以将筛分所需的时间大约减少一半。
• 不要使用整个int对于标志，使用位或至少chars。这提供了更好的缓存局部性和进一步的加速。