2

这是问题的链接。

该问题询问形式为1/x + 1/y = 1/z（其中z = n!）的丢番图方程的解数。重新排列给定的方程清楚地表明答案是z 2的因子数。

所以问题归结为找到n的因子数！2（n阶乘平方）。

我的算法如下

  1. 使用 Sieve of Eratosthenes 算法为所有素数 <= n 制作布尔查找表。
  2. 遍历所有素数P <= n并在 n 中找到它的指数！. 我使用阶跃函数公式做到了这一点。设指数为K，则为P在n 中的指数！2将是2K。
  3. 使用步骤 2 使用标准公式计算因子数。

对于n = 10 6的最坏情况输入，我的 c 代码在 0.056 秒内给出答案。我猜复杂度不会比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;
}
4

1 回答 1

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对标志使用整体，使用位或至少chars。这提供了更好的缓存局部性和进一步的加速。
于 2012-04-16T20:02:46.730 回答