346 Strong Repunits

Problem 346

7 有一个特殊的性质，以 2 为基底是 111，以 6 为基底是 11。也就是说，基底 的情况下，整数 能够至少写成两个基底的循环单元。我们称这种整数位 Strong Repunits，强循环整数。50 以内， 这些都是满足该性质的。

题目为了检验算法和实现，给出了 1000 以内强循环整数的和是15864。

求 以内的强循环整数之和。

想知道一个整数是不是强循环整数比较难，反过来，我们构造强循环整数比较容易。

首先，任何一个数 ，都可以循环整数的形式 11，其基底是。

那么我们从基底 开始，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 那个判断，就是说，以 为基底的数 111 已经比 还大了，计算可以停止了。

第二个小问题，最后求和之前要调用 Distinct() 函数，因为会存在一些数，即能写成以 为基底， 个 1，也可以写成以 为基底， 个 1，那么这个数往 List 里面插入了两次，当然，repunits 用 Set 就不存在这个问题了。

第三个小问题，求以 为基底， 个 1 的数的大小，不用每个 1 挨着求多少次方再加起来，使用等比数列的求和公式，直接算答案比较省事。

最后，说我踩得一个坑，注意，求 的 次方的那个函数，我使用了 Utils.Pow(b, n)，我使用二分法自己实现了一个简单的 Pow 函数。因为 C# 自带的参数是 double，求值的时候会有精度损失，特别是 的 次方很大的时候，可能会少一点点或者多一点点，一旦强转成 long 的话，会多一或者少一，导致结果不正确。

开始的时候，计算了 1000 以内强循环整数的和，和题目给的一样，但是算 以内的值时，答案就不对了，想了半天，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;
    }
}