如何优化我的代码,找到所有可能的积分三角形的所有积分中位数的计数<= b <= c <= 100000？

Question

我正在从欧拉项目问题513,积分中位数来解决这个问题:

ABC是一个整数的三角形,边长为a≤b≤c.mc是连接C和AB中点的中位数.F(n)是具有c≤n的这种三角形的数量,其中mc也具有整数长度.F(10)= 3且F(50)= 165.

找到F(100000).

分析:

1. a <= b <= c <= n == 100000
2. ABC是一个三角形,所以它应该: abs(a-b) < c < a+b
3. Mc = sqrt(2 * a^2+ 2 * b^2 - c^2) / 2 维基百科
4. Mc是整数,所以2 * a^2+ 2 * b^2 - c^2应该是一个完美的正方形,可以被4整除.

码:

#include <stdio.h>
#include <math.h>

#define N 100000
#define MAX(a,b) (((a)>(b))?(a):(b))

void main(){
    unsigned long int count = 0;
    unsigned long int a,b,c;
    double mc;

    for (a = 1; a <= N; a++) {
        printf("%lu\n", a);
        for (b = a; b <= N; b++)
            for (c = MAX(b, abs(b-a)); c <=N && c < a+b; c++){
                mc = sqrt(2 *a *a + 2 * b * b - c * c)/2.0;
                if (mc-(unsigned long)mc == 0)
                    count++;
            }
    }
     printf("\ncpt == %lu\n", count);

}

问题:

它适用于小型,n但解决方案的复杂性太高,我认为它O(n^3)(我错了吗？)这将需要数天n = 100000.

无论是采用数学方法还是算法方法,我怎样才能改善这一点？

更新

我得到了这些建议:

• 计算/ loop a外部的功率和外部环路的功率.这略微改善了性能.bcbc
• c不能奇怪.然后a,b必须有相同的平价.这提高了4倍的性能.
• 使用线程在许多核心上划分工作.它可以通过接近核心数的因子来改善.
• 在math.stackexchange中发布的数学解法.它声称O(N^5/2)有一个基本的解决方案,可以O(N^2)通过使用O(N^2)内存来实现.我还没测试过.

Answer 1

由于这是一个欧拉计划问题，您应该能够在现代计算机上用大约一分钟的计算时间来完成它。他们并不总是坚持这一点，但这表明如果常量不太糟糕，k*n^2或的运行时间可能很好，但可能不是或。k*n^2*log(n)k*n^2.5k*n^3

正如 SleuthEye 所评论的，c 边必须是偶数，否则平方根的内部必须是奇数，因此开平方根并除以 2 不能得到整数。

您可以将方程简化为4(mc^2+(c/2)^2) = 2(a^2+b^2)。

这是一种方法：创建两个字典，左字典和右字典。对于每个，让键为等式一侧的可能值，并让值作为生成键的对(mc,c/2)或的列表。(a,b)对于正确的字典，我们只需要考虑 wherea和b具有相同的奇偶性，以及 where 1<=a<=b<=n。对于左边，我们只需要考虑1<=c/2<=n/2和1<=mc<=sqrt(3)/2 n由于4mc^2 = 2a^2+2b^2-c^2 <= 3b^2 <=3n^2。

然后遍历可能的键，并比较每个字典中值的元素，找到兼容对的数量，((mc,c/2),(a,b))其中b <= c < a+b。这个内部步骤不是恒定时间，但列表的最大和平均长度不会太长。将 n 写为两个平方和的方法大致对应于在高斯整数中对 n 进行因式分解的方法（最多单位），并且正如整数的最大因数数量不会增长得太快一样，同样如此在高斯整数中。这一步O(n^epsilon)对于任何epsilon>0. 因此，总运行时间是O(n^(2+epsilon))对于任何epsilon>0.

在实践中，如果内存不足，您可以构造部分字典，其中键被限制在特定范围内。这也很好地并行化。