算法的优化[关闭](Optimization of Algorithm [closed])

这里是链接到的问题。

该问题询问到窗体的不定方程解的数目（其中 显然重新排列给出的公式告诉答案是的因子数目。

所以，问题归结为寻找要素的数量 阶乘的平方）。

我的算法如下

1. 让所有的素数布尔查找表<= N使用埃拉托色尼算法的筛。
2. 遍历所有素数 <= 和找到其在指数 。 我这样做是使用阶梯函数公式。 让指数是那么在 的指数 将
3. 使用与标准配方因素步骤2计算数量。

对于的最坏的情况下输入我的C代码给出0.056s答案。 我猜的复杂性是没有办法比的 但是，当我提交了网站上的代码，我可以随着时间的超限只传递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秒。 这给了更好的缓存局部性和进一步加速。

文章来源: Optimization of Algorithm [closed]