Cardano Triplet问题

一个有趣的问题：

A triplet of positive integers (a,b,c) is called a Cardano Triplet if it satisfies the condition:

For example, (2,1,5) is a Cardano Triplet.

There exist 149 Cardano Triplets for which a+b+c  1000.

Find how many Cardano Triplets exist such that a+b+c  110,000,000.

首先可以把问题的表达式可以化成：

8a^3 + 15a^2 + 6a - 1 = 27b^2*c

然后使用穷举法遍历a，b，c可以取的所有值，判断是否满足上述表达式：

int CardanoTriplets1(int Max)

{

    long a, b, c;

    long count = 0;

    for(a = 1; a < Max; a++)

    {

        for(b = 1; b < Max - a; b++)

        {

            for(c = 1; c <= Max - a - b; c++)

            {

                if((8*a*a*a + 15*a*a + 6*a - 1) == 27*b*b*c)

                {

                    count++;

                }    

            }    

        }     

    }    

    return count;

} 

可以根据问题的性质对算法稍作改进：

第一，可以证明a满足a = 2 (mod 3)或者2a = 1 (mod 3)，证明略

第二，给定a的值以后，有：

b^2*c = S

b + c = K

S和K都是a的表达式，从上面两式可以求出b的一个下界和上界：

 4 * S / K^2 <= b <= S^0.5

由此可以给出程序：

int CardanoTriplets2(int Max)

{

    long a, b, c;

    long count = 0;

    double S, K, b_min, b_max;

    double t;

    for(a = 1; a < Max; a++)

    {

        if(a % 3 == 2)

        {

            K = Max - a;

            t = 1.0 - 2.0 * a;

            S = a * a - t*t*t/27.0;

            b_min = 4.0 * S / K / K - 1;

            b_max = sqrt(S) + 1;

            if(b_min < 1) b_min = 1; 

            if(b_max > K) b_max = K;  

            for(b = (long)b_min; b <= (long)b_max; b++)

            {

                c = (long)S / b / b;

                if(c >= 1 && (b * b * c) == S && (b + c) <= K)

                {

                    //cout<<"("<<<","<<<","< <<")"<

                    count++;

                }           

            }      

        }    

    }     

    return count;

}