算法的优化 [英] Optimization of Algorithm

问题描述

下面是链接的问题。

问题问到窗体的丢番图方程解的个数 1 / X + 1 / Y = 1 / Z （其中， Z = N！）。显然重新排列给定的公式告诉答案的以Z ² 因子的数量。

所以，问题归结找到的因子数名词！ ²

我的算法如下

1. 请对所有素数℃的布尔查找表= N使用埃拉托色尼算法的筛
。

2. 遍历所有素数 P ＆LT;！= 名词和找到其指数 N 。我这样做是使用阶梯函数公式。让指数是 K ，那么的指数 P 在名词！ ² 将 2K


3. 使用与标准公式因素第2步计算数量。

有关的最坏的情况下输入 N = 10 ⁶ ，我的C code给出0.056s答案。
我猜的复杂性是没有办法大于为O（n LG N）。
但是，当我提交了code在网站上，我可以随着时间的超限只传递3/15测试用例与其他部分的判决。

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

code迄今：

 的#include＆LT;＆stdio.h中GT;
＃包括LT＆;＆string.h中GT;＃定义ULL无符号长long int类型
＃定义MAXN 1000010
＃定义MOD 1000007INT isPrime [MAXN]ULL解决（INT N）{
    INT I，J，F;
    ULL RES = 1;
    memset的（isPrime，1，MAXN *的sizeof（INT））;
    isPrime [0] = isPrime [1] = 0;
    对于（i = 2; I * I＆LT; = N; ++ I）
        如果（isPrime [I]）
            为（J = I * I，J＆LT; = N; J + = 1）
                isPrime [J] = 0;
    对于（i = 2; I＆LT; = N; ++ I）{
        如果（isPrime [I]）{
            为（J = I，F = 0; J＆LT; = N;Ĵ* = I）
                F + = N / J;
            F =（（F＆所述;＆所述; 1）+ 1）％MOD;
            RES =（RES * F）％MOD;
        }
    }
    返回RES％MOD;
}诠释主（）{
    INT N;
    scanf函数（％d个，＆安培; N）;
    的printf（％LLU \\ n，解决了（N））;
    返回0;
}
 

解决方案

在这里你有一个 INT 溢出：

 为（J = I，F = 0; J＆LT; = N;Ĵ* = I）
 

如果 46340＆LT; I＆LT; 65536 ，并为许多较大的 I ，在第二次迭代Ĵ将是负面的，如果溢出绕回（这是不确定的行为，所以什么事情都可能发生）。

与例如更换。

 为（J = N / I，F = 0; J＆GT; 0;焦耳/ = 1）{
    F + = j的;
}
 

然而，这是，不可能的，额外的迭代由于溢出会导致一个超出时间限制，这将有可能只会导致错误的结果。

所以一般的建议是

• 筛只有奇数，或许还可以消除从筛3的倍数。消除来自筛子奇数大致半部筛所需的时间。


• 请不要使用整个 INT 为标志，使用比特或至少字符秒。这给了更好的缓存局部性和进一步加速。

Here is the link to the problem.

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 problem boils to find the number of factors of n!².

My algorithm is as follows

1. Make a boolean look up table for all primes <= n using Sieve of Eratosthenes algorithm.
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. Using step 2 calculate number of factors with the standard formula.

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.

I need some hint for optimizing this algorithm.

Code so far:

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

解决方案

You have an int overflow here:

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

If 46340 < i < 65536 and for many larger i, in the second iteration j will be negative if overflow wraps around (it is undefined behaviour, so anything could happen).

Replace it with e.g.

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

It is, however, unlikely that the extra iterations due to the overflow would cause a "time limit exceeded", that will likely only cause wrong results.

So the generic advice is

• Sieve only odd numbers, perhaps also eliminate multiples of 3 from the sieve. Eliminating the odd numbers from the sieve roughly halves the time needed to sieve.
• Don't use an entire int for the flags, use bits or at least chars. That gives better cache locality and a further speedup.

这篇关于算法的优化的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！