欧拉项目 | 346题 | 强循环整数

题目链接

7有一个特殊的性质，以2为基底是111，以6为基底是11。也就是说，基底b > 1的情况下，整数n能够至少写成两个基底的循环整数。我们称这种整数位Strong Repunits，强循环整数。50以内，{1,7,13,15,21,31,40,43}这些都是满足该性质的。
题目为了检验你的算法，给出了1000以内强循环整数的和是15864。
求，10 ^ 12以内的强循环整数之和。

想知道一个整数是不是强循环整数比较难，反过来，我们构造强循环整数比较容易。
首先，任何一个数m，都可以循环整数的形式11，其基底是m-1。
那么我们从基底b = 2开始，1的个数从n = 3开始，开始构造循环整数，这样的循环整数一定是强循环整数，因为有一个基底是m-1的11。

首先贴出代码，再来解释一些小策略和我踩过的坑。

var repunits = new List<long>();
var MAX = Utils.Pow(10, 12);

int b = 2;
while (true)
{
    int n = 3; // count of 1
    while (true)
    {
        long sum = (long)((Utils.Pow(b, n) - 1) / (b - 1));
        if (sum >= MAX)
        {
            break;
        }

        repunits.Add(sum);
        n++;
    }

    if (n == 3)
    {
        break;
    }

    b++;
}

return repunits.Distinct().Sum() + 1;

第一个小问题，if n == 3那个判断，就是说，以b为基底的数111已经比10 ^ 12还大了，计算可以停止了。
第二个小问题，最后求和之前要调用Distinct()函数，因为会存在一些数，即能写成以b1为基底，n1个1，也可以写成以b2为基底，n2个1，那么这个数往List里面插入了两次，当然，repunits用Set就不存在这个问题了。
第三个小问题，求以b为基底，n个1的数的大小，不用每个1挨着求多少次方再加起来，使用等比数列的求和公式，直接算答案比较省事。

最后，说我踩得一个坑，注意，求b的n次方的那个函数，我使用了Utils.Pow(b, n)，我使用二分法自己实现了一个简单的Pow函数。因为C#自带的参数是double，求值的时候会有精度损失，特别是b的n次方很大的时候，可能会少一点点或者多一点点，一旦强转成long的话，会多一或者少一，导致结果不正确。
开始的时候，计算了1000以内强循环整数的和，和题目给的一样，但是算10 ^ 12以内的值时，答案就不对了，想了半天，debug了一会，才发现是精度问题。于是乎，自己实现了一个，返回值是BigInteger，代码写得稍微啰嗦了点，但是很好的表现了二分法的内涵，哈哈。

public static BigInteger Pow(int b, int n)
{
    if (n == 1)
    {
        return b;
    }

    var half = Pow(b, n / 2);
    if (n % 2 == 0)
    {
        return half * half;
    }
    else
    {
        return half * half * b;
    }
}