2.4.25

2.4.25 #

解答 #

官方实现：https://algs4.cs.princeton.edu/24pq/CubeSum.java.html

注意这道题并不是要打印所有的 $a^3+b^3$ 的结果，而是需要找到 $a^3+b^3=c^3+d^3$ 这个丢番图方程的解。

因此在官方实现的基础上，每次取出最小值之后和之前的最小值比较，如果相等则输出对应的组合。

关键代码如下：

CubeSum prev = new CubeSum(-1, -1);
long pairCount = 0;
while (!pq.IsEmpty())
{
    CubeSum s = pq.DelMin();
    if (s.sum == prev.sum)			// 如果与之前的数相等
    {
        Console.WriteLine(s + " = " + prev.i + "^3 + " + prev.j + "^3");
        pairCount++;
    }         
    if (s.j < n)
        pq.Insert(new CubeSum(s.i, s.j + 1));
    prev = s;
}

当然，对于 n=10^6 来说结果会非常大，程序的运行时间需要以天为单位计算（约 14 天）。

n=10^4 时，总共可以找到 41570 对数据。（result10K.txt, 下载大小 506 KB，解压后 1.93 MB）

n=10^5 时，总共可以找到 895023 对数据。(result100K.txt，下载大小 12.7 MB，解压后 47.5 MB)

n=10^6 时，总共可以找到 16953323 对数据。（result1M.txt，下载大小 280 MB，解压后 0.98 GB）

结果下载链接：百度云、Onedrive

代码 #

CubeSum.cs

internal class CubeSum : IComparable<CubeSum>
{
    /// <summary>
    /// 立方和。
    /// </summary>
    internal readonly long Sum;
    /// <summary>
    /// 第一个数。
    /// </summary>
    internal readonly long I;
    /// <summary>
    /// 第二个数。
    /// </summary>
    internal readonly long J;

    /// <summary>
    /// 建立一个立方和类。
    /// </summary>
    /// <param name="i">立方和的第一个数。</param>
    /// <param name="j">立方和的第二个数。</param>
    public CubeSum(long i, long j)
    {
        Sum = i * i * i + j * j * j;
        this.I = i;
        this.J = j;
    }

    /// <summary>
    /// 比较两个立方和的大小，返回 1, 0, -1 中的一个。
    /// </summary>
    /// <param name="other">需要与之比较的另一个数。</param>
    /// <returns></returns>
    public int CompareTo(CubeSum other)
    {
        return Sum.CompareTo(other.Sum);
    }

    /// <summary>
    /// 返回 "sum = i^3 + j^3" 形式的字符串。
    /// </summary>
    /// <returns></returns>
    public override string ToString()
    {
        return Sum + " = " + I + "^3 + " + J + "^3";
    }
}

主程序

var n = 1000000;

var pq = new MinPq<CubeSum>();
Console.WriteLine("正在初始化");
for (var i = 0; i <= n; i++)
{
    pq.Insert(new CubeSum(i, i));
}

var ostream = new FileStream("./result.txt", FileMode.Create, FileAccess.Write);
var sw = new StreamWriter(ostream);
Console.WriteLine("正在写入文件……");
var prev = new CubeSum(-1, -1);
long pairCount = 0;
while (!pq.IsEmpty())
{
    var s = pq.DelMin();
    if (s.Sum == prev.Sum)
    {
        sw.WriteLine(s + " = " + prev.I + "^3 + " + prev.J + "^3");
        pairCount++;
    }

    if (s.J < n)
        pq.Insert(new CubeSum(s.I, s.J + 1));
    prev = s;
}

sw.WriteLine("共找到" + pairCount + "对数据");
Console.WriteLine("共找到" + pairCount + "对数据");
sw.Close();
Console.WriteLine("结果已经保存到程序所在目录下的 result.txt 文件中");

另请参阅 #

Diophantine Equation-3rd Powers - Wolfram MathWorld

PriorityQueue 库