原题链接

$2^7=128$是第一个以12开头的2的幂次数。下一个是$2^{80}$。
$p(L,n)$表示满足$2^j$以$L$开头的第$n$个$j$的值。所以$p(12,1)=7$，$p(12,2)=80$。
题中给出$p(123,45)=12710$以验证程序。
求$p(123,678910)$。

$2^{12710}$就是一个比较大的数字，如果使用BigInteger.ToString检查其是否以123开头还好，但是这才第45个以123开头的幂次，第678910个满足条件的幂次要大的多得多，时间也要长太多，所以我们需要一个速度更快的方式来检查。

题目链接

$p_n$表示第$n$个质数，$r$是$(p_n-1)^n+(p_n+1)^n$模$p_n^2$的余数。
求满足余数$r$超过$10^{10}$的$n$的最小值。

题目链接

$s(n)$的定义是数字之和是$n$的最小值，比如$s(10)=19$。
$S(k)=\sum_{n=1}^ks(n)$，题中给出$S(20)=1074$，可以用于检测程序是否基本正确。
$f_i$是斐波那契数列。
问题是求$\sum_{i=2}^{90}S(f_i)$模1000000007。

斐波那契数列以指数速度增长，所以暴力法肯定是不行的（$f_{90}$快接近long的表示上限了），那么需要在常数或者对数时间复杂度的算出$S(k)$的算法。
$s(n)$其实很容易想，数字最小，那么就是高位的值越小越好，那么低位的值都是9即可。
有了$s(n)$，我们就可以推导一下$S(k)$了。

100题链接

正整数方程$\frac{1}{x}+\frac{1}{y}=\frac{1}{n}$。如果$n=1260$，那么有113个不同的解，这个解的数量超过100的最小的$n$值。
求不通解的数量超过4百万的$n$的最小值。

$x$和$y$必须大于$n$，否则$1/x$或$1/y$就比$1/n$大了。所以不妨令$x=n+a,y=n+b$，其中$a,b$也都是整数。带入原式，我们可以得到$n^2=ab$。所以原方程就变成了$n^2$有多少种方式分解成两数之积。

95题链接

28有4个不包含自身的因数1 2 4 7，其和恰好是28，我们称之为完美数。
220不包含自身的的因数之和是284，284不包含自身的因数之和是220，形成了一个长度为2的链，也称之为亲和数。
从12496能形成一个长度为5的链：12496 -> 14288 -> 15472 -> 14536 -> 14264 (-> 12496 -> …)。
找到一个所有数值都不超过一百万的最长的链，问其中最小的数。

首先，我们要快速找到每个数对应的因数之和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

var numberToDivisorSum = new List<int>(MAX + 1);
for (int i = 0; i <= MAX; i++)
{
    // 1 is divisor
    numberToDivisorSum.Add(1);
}

// i is a factor
for (int i = 2; i <= MAX / 2; i++)
{
    // excluding the number itself, so j starts from 2
    for (int j = 2; j <= MAX / 2; j++)
    {
        if (i * j > MAX)
        {
            break;
        }

        numberToDivisorSum[i * j] += i;
    }
}

接下来计算每个数开始能够形成的链的长度，找到最长链所对应的最小的数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

var numberToLength = new List<int>(MAX + 1) { 0 };
int longest = -1;
int index = -1;
for (int i = 1; i <= MAX; i++)
{
    numberToLength.Add(0);
    if (numberToDivisorSum[i] != -1)
    {
        int length = GetChainLength(i, numberToDivisorSum);
        numberToLength[i] = length;
        if (length > longest)
        {
            index = i;
            longest = length;
        }
    }
}

private static int GetChainLength(int number, List<int> numberToDivisorSum)
{
    var chain = new List<int>();
    int cur = number;
    while (true)
    {
        chain.Add(cur);
        int next = numberToDivisorSum[cur];
        if (next > MAX || next == -1)
        {
            foreach (var s in chain)
            {
                if (s > number)
                {
                    numberToDivisorSum[s] = -1;
                }
            }
            return -1;
        }

        if (chain.Contains(next) && number != next)
        {
            return -1;
        }

        if (next == number)
        {
            foreach (var s in chain)
            {
                if (s > number)
                {
                    numberToDivisorSum[s] = -1;
                }
            }

            return chain.Count;
        }

        cur = next;
    }
}

这里有一个有点trick的地方，如果一个链形成了（已经知道最小数了），或者因数之和比MAX要大导致无法形成一个链，那么把当前number之后的数都标记一下，在外层调用函数的for循环里面跳过，这样子大概能节省10%的时间吧。

145题链接

有这样一些数n，和所以数字逆着写的数reverse(n)之和的所有数字都是奇数。比如36+63=99，409+904=1313等等，这些数我们称之为可逆数。有一个限制条件就是开头不能是0。
问题是，小于十亿（1,000,000,000)的数中有多个可逆数。

这道题可以通过分类讨论来解决。
首先n的长度是奇数和偶数明显是两类，因为这意味着有没有正好居于中间的数，对于奇数长度来说，有，且反过来还是该数字。

我们先来考虑长度是偶数的时候。

长度为2的时候，不妨把该数写作AB，其逆就是BA。以A+B是否大于等于10来讨论。
大于等于10的情况，不妨令A+B=1C，那么AB+BA=1(C+1)C，C和C+1奇偶性必然不同，不可能数字都是奇数。
小于10的情况，那么A+B是奇数。A是偶数，可选2,4,6,8，B是奇数，可选1,3,5,7,9，之和小于10的情况一共10种可能性。反之，A是奇数，B是偶数，也是10种。
所以长度为2的可逆数一共20个。

长度为4的时候，该数可写作ABCD，其逆就是DCBA。以A+D是否大于等于10来讨论。
大于等于10的情况，不妨令A+B=1E。若B+C大于等于10，和最后一位是E，右起第四位是1+E，不可能都是奇数；若B+C小于10，不能是9，否则和的右起第二位是0，不满足题意，如果是其他奇数，右起第二位和1+B+C，而右起第三位是B+C，也不可能同时是奇数。
小于10的情况，A和D的取值可能性有20种，中间的BC退化为长度为2的情况，取值的可能性有30种（偶数可以为0，因为不打头了），利用乘法原则，共有600个可逆数。
所以长度为4的可逆数一共600个。

长度为6的时候，该数可以写作ABCDEF，其逆就是FEDCBA。以A+F是否可以大于等于10来讨论。
大于等于10的情况，原理和4位时一样，B+E不能大于等于10。能小于10吗？为了保证B+E得到的值和E+B+1得到的值一样，那么C+D就要大于10。但是E+B不进位，而D+C进位，导致右起3，4位一定不能同时是奇数。
小于10的情况，中间4个数回到了上一种情况，所以可能性是20*30*30=18,000。
所以长度为6的可逆数一共是18,000个。

长度为8的时候，该数可以写作ABCDEFGH，其逆就是HGFEDCBA。同样，以A+H是否可以大于等于10来讨论。
在大于等于10的情况下，原理同上，B+G不能大于等于10，那么B+G就只能小于10了。同上，C+F就要大于等于10。为了使得中间两位的奇偶性一致，那么E+D要大于10，结果就是右起第三位数字是C+F模10（因为B+G小于10），而右起第六位数字是C+F+1模10，这俩不可能同时是奇数。
小于10的情况，中间六个数字回到了上一种情况，所以可逆数是20*30*30*30=540,000。
所以长度为8的可逆数一共是540,000个。

现在来讨论n的长度为奇数。
如果长度是1，反过来是其本身，那么和是偶数，不符合题意。

长度是3，可写作ABC，可逆数是CBA。中间数字的和是偶数，那么A+C必须大于10，为了右起第一位和第三位奇偶性相同，那么2B不能进位，所以B要小于等于4，那么B有五种可取值；我们现在讨论A和C，A是奇数1,3,5,7,9，C是偶数2,4,6,8，其和大于10的可能性有10中可能性，A是偶数C是奇数也有10种，那么可逆数是5*(10+10)=100。

长度是5时，可写作ABCDE，可逆数是EDCBA。中间是2C，所以B+D是大于等于10的，右起第一位是E+A，但是右起第五位是A+E+1，不可能同时是奇数，所以n的长度不可能是5。

长度为7时，可写作ABCDEFG，可逆数时GFEDCBA。中间是2D，所以C+E时大于等于10的。根据前面的分析，B+F必须小于10；进而2D要小于10。右起第六位会接受来此C+E的进位，那么右起第二位也必须接受一个进位，所以A+G必须大于10。2D小于10得出D有5种可能性，A+G大于10且和为奇数共有20种可能性，C+E大于10且和为奇数也有20种，B+F小于10且为偶数的可能性有25种。所以可逆数是5*20*20*25=50,000。

长度为9的时候，可写作ABCDEFGHI，其可逆数是IHGFEDCBA。由前面的分析可知D+F要大于等于10，那么为了让右起第三位G+C和右起第七位C+G同时为奇数，那么H+B也必须大于10，那么A+I得到B+H的进位，无法和右起第一位I+A同奇偶，矛盾，所以长度不能是9。

综上，小于十亿的可逆数是608720个。

Problem 348

很多数能够写成一个平方数和一个立方数之和的形式，其中一些可能会有多种组合形式。
有一些数有4种组合形式，且它是一个回文数。比如5229225是一个回文数，能写成四种组合形式：

1
2
3
4

2285^2 + 20^3
2223^2 + 66^3
1810^2 + 125^3
1197^2 + 156^3

找到前五小的这种数，求和。

一个数是否能拆解成一个平方数和一个立方数之和是比较难的问题，但是构造一个这样的数就比较简单了。我开始假设在int范围内就至少有五个满足题意的数。
下面这段代码就会找出所有是一个平方数和一个立方数之和的回文数，并且统计了它们出现的次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

var counts = new Dictionary<int, int>();
for (int i = 2; i < Math.Sqrt(int.MaxValue); i++)
{
    for (int j = 2; j < 1291; j++)
    {
        long sum = i * i + j * j * j;
        if (sum > int.MaxValue)
        {
            break;
        }

        int s = (int)sum;
        if (Utils.IsPalindrome(s.ToString()))
        {
            if (counts.ContainsKey(s))
            {
                counts[s]++;
            }
            else
            {
                counts[s] = 1;
            }
        }
    }
}

然后找出出现次数为4的回文数，排序，取前五，求和。

1
2
3
4

var candidates = counts.Where(pair => pair.Value == 4).Select(pair => pair.Key).ToList();
candidates.Sort();

return candidates.Take(5).Sum();

Problem 203

二项式系数可以写成如下帕斯卡三角的形式

前八排有12个不同的数：1, 2, 3, 4, 5, 6, 7, 10, 15, 20, 21 和 35。
Squarefree的意思是不能被任何质数的平方整除。前八排的数字里面，4和20不是Squarefree的，因为它们能被质数2的平方整除。
求帕斯卡三角前51排不重复的Squarefree的数之和。

我们先来估计下最大的数是多少，然后考虑用什么类型表示，第五十一行其实是n=50，那么最大的是数$$C_n^k=C_{50}^{25}=\frac{50!}{25!25!}=126,410,606,437,752$$，long就足够了。
首先我们拿到前51排的数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

var rows = new List<long[]>();
for (int i = 0; i < 51; i++)
{
    long[] row = new long[i + 1];
    for (int j = 0; j < row.Length; j++)
    {
        if (j == 0 || j == row.Length - 1)
        {
            row[j] = 1;
        }
        else
        {
            var lastRow = rows[i - 1];
            row[j] = lastRow[j - 1] + lastRow[j];
        }
    }

    rows.Add(row);
}

下一步去重。

1

var candidates = rows.SelectMany(l => l).Distinct().ToList();

要考虑那些质数的平方呢？仔细想下前51排数的性质，只需要考虑很少几个数就足够了。

1

var smallPrimeSquare = new int[] { 4, 9, 25, 49 };

如果某个数能被下一个质数的平方121整除，那么n至少要是22，这样子二项式系数的分子上才会出现2个11，但是不管k怎么取，分母上都至少有一个11这个因数。那么n至少要是33了，不管k怎么取，分子上都至少有两个11这个因数。那么n至少要是44了，同理，也无法被121整除。总结下，分母上11的因数的个数至少是分子上11的因数的个数减一。其实，结论很容易直接证明的。
那么为什么需要考虑49呢？很简单，49包含了两个7，那么n取49和50的时候，有可能分子因数7的个数能够比分母多两个。那么该数就能被49整除，进而不是Squarefree的。
最后，排除Squarefree的数字再求和即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

candidates = candidates.Where(l =>
{
    foreach (var square in smallPrimeSquare)
    {
        if (l % square == 0)
        {
            return false;
        }
    }

    return true;
}).ToList();

return candidates.Sum();

179题链接

14和15有同样个数的正因数，14有四个，1,2,7,14；15也有四个，1,3,5,15。求在1到10的7次方之间，有多少个有相同个数正因数的连续的整数？

正向求解的方式就是分解质因数，然后计算得到因数个数，这个操作看似很快，但是还是稍微有点耗时，感觉不太行。
于是乎，走向另外一条路，每找到一个因数，就加一。

1
2
3
4
5
6
7
8

int[] numberOfDivisors = new int[N + 1];
for (int i = 1; i <= N; i++)
{
    for (int j = i; j <= N; j += i)
    {
        numberOfDivisors[j]++;
    }
}

i就是因数，若干倍的j就包含一个因数i了。

知道了每个数的因数个数就简单了，看连续两个数的因数个数是否相等即可。

1
2
3
4
5
6
7
8
9
10

int count = 0;
for (int i = 2; i < N; i++)
{
    if (numberOfDivisors[i] == numberOfDivisors[i + 1])
    {
        count++;
    }
}

return count;

Problem 125

回文数595能够被写成连续几个数字的平方的和：
$$
595=6^2+7^2+8^2+9^2+10^2+11^2+12^2
$$

连续数字必须是正数，所以1=0+1被排除在外。
题目告诉我们小于1000的数字中，有11个满足题目所述条件，其之和是4164，这可以用来检测我们的程序是否正确。

求小于10^8的数中，所以能够写成连续数字平方和的回文数之和。

欧拉里面这种题目的套路就是正向构造符合题意的数字。因为想要判定一个数能否写成连续数字之后比较困难，但是构造一个连续数字平方和的数就容易多了。
我们先计算出一系列的平方数，多少个呢？由于连续数字之和，那么最少也要两个数字，所以我们构造的最大平方数是MAX的一半就足够了。

1
2

int MAX = 100000000;
var squars = Enumerable.Range(1, (int)Math.Sqrt(MAX / 2)).Select(i => i * i).ToArray();

两层for循环来构造连续数字之和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

var candidates = new List<long>();
for (int i = 0; i < squars.Length - 1; i++)
{
    long sum = squars[i];
    for (int j = i + 1; j < squars.Length; j++)
    {
        if (sum + squars[j] < MAX)
        {
            sum += squars[j];
            candidates.Add(sum);
        }
        else
        {
            break;
        }
    }
}

这里面有一小撮重复的数字，去重，然后判断是否是回文数字，求和。

1

return candidates.Distinct().Where(l => Utils.IsPalindrome(l.ToString())).Sum();