欧拉项目 | 64题 | 连分数的周期性

Problem 64

一个数的平方根可以写成连分数，形式就是题目中描述的那样。a0,a1,a2,a3…可以看作是一个数列，这个数列很快就有周期性了，比如题目中的例子，sqrt(23)写成连分数，取数列a就是4,1,3,1,8,1,3…可以看出来，循环节是1318，周期是4。

问题是要求，小于10000的所有整数，有多少个周期是奇数的呢？

求解这个题目，关键是，给一个数N，如何求得a0,a1,a2,a3…
祭出伟大的维基百科：Continued_fraction_expansion
可以略过推导部分，直接看Algorithm实现就好了。

好了，我们现在能求得了这个数列，如何判定周期呢？
从算法上我们可以看到，m d a三个数是迭代计算的，也就是说，第n+1次的m d a三个数字是有第n次的m d a决定的，因为sqrt(S)不变。如果有两次的m d a一样，那么它们后续都一样。
我的做法是拿一个list，把m d a作为一个组放进去，每次计算得到一组新的m d a，就去list里面查找一下，如果找不到，说明这个是新的pattern，放到list里面，如果找到了，那么这次的序数减去上次的序数，就是周期了。

private static int GetPeriod(int S)
{
    int a0 = (int)Math.Sqrt(S);
    int m = 0;
    int d = 1;
    int a = a0;
    var periods = new List<Tuple<int, int, int>>();
    while (true)
    {
        m = d * a - m;
        d = (S - m * m) / d;
        a = (a0 + m) / d;
        var cur = Tuple.Create(m, d, a);
        int index = periods.IndexOf(cur);
        if (index >= 0)
        {
            return periods.Count - index;
        }
        else
        {
            periods.Add(cur);
        }
    }
}

有了计算周期的函数，下面的事情就好办了，遍历1-10000这一万个数字就好了，不过，我们可以可以先排除完全平方数，因为它们只有a0，没有后续的a1,a2等等。

int count = 0;

var l1 = Enumerable.Range(1, 10000);
var l2 = Enumerable.Range(1, 100).Select(x => x * x);
var candidates = l1.Except(l2);

foreach (var c in candidates)
{
    if (GetPeriod(c) % 2 != 0)
    {
        count++;
    }
}

return count;