一点一点前进...

0%

欧拉项目 | 66题 | 丢番图方程

发表于 分类于 ， Disqus：

66题链接

二次丢番图方程如下
$$
x^2 – Dy^2 = 1
$$
当D = 13时，x的最小解是
$$
649^2 – 13*180^2 = 1
$$
当D是平方数时，无解。
题目中给出了几个示例，当D = {2, 3, 5, 6, 7}时，列出了x的最小解，其中最小解的最大值是x = 9，对应的D = 5
找到这样一个D，使得x最小解是最大值，其中D ≤ 1000。

如果我们能对于某个D，快速找到最小解x。这个题就很容易了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
List<int> D = Enumerable.Range(1, 1000)
                        .Where(i => Math.Pow((int)Math.Sqrt(i), 2) != i)
                        .ToList();
BigInteger max = 0;
long ret = 0;
foreach (var d in D)
{
    BigInteger cur = GetX(d);
    if (max < cur)
    {
        max = cur;
        ret = d;
    }
}

return ret;

现在问题就是如何GetX。论文An Algorithm to Solve a Pell Equation给出了一种快速的解法。

接下来，照猫画虎，把算法实现一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private static BigInteger GetX(int n)
{
    List<BigInteger> a = new List<BigInteger>() { 0, 1 };
    List<BigInteger> b = new List<BigInteger>() { 1, 0 };
    List<int> c = new List<int>() { n, 1 };

    int i = 1;
    do
    {
        int q = (int)((Math.Sqrt(n - c[i - 1] * c[i]) + Math.Sqrt(n)) / c[i]);
        c.Add((int)(2 * q * Math.Sqrt(n - c[i - 1] * c[i]) + c[i - 1] - q * q * c[i]));
        a.Add(q * a[i] + a[i - 1]);
        b.Add(q * b[i] + b[i - 1]);
        i++;
    } while (a.Last() * a.Last() - n * b.Last() * b.Last() != 1);

    return a.Last();
}

为什么要用BigInteger类型呢？虽然D不大，但是x和y的值可能会很大，甚至超过long的表示范围。