不知不觉一个季度过去了，是该总结过去一个季度做了什么，然后例行展望下下个季度。

数学，英语，计算机，其他，四个部分。由后向前说吧。
年初的时候规划了这一整年的书籍和公开课。人类简史已经读完，还需要再花点时间把笔记总结一下；可汗的微观经济学也看了，目前在看宏观经济学；耶鲁的物理基础公开课1也看完了，收获颇丰，正在看2；上交的数学之旅也看几课了，快完了；论美国的民主也已提上日程，很久没有读过这么厚这么多字的书了。
年初计划的是，如果用掉之前需要弥补的小20小时，这些应该都能搞定。现在看来，时间上绰绰有余，后续有条不紊的继续就好。

计算机，过去的一个季度，分布式看了一点点；C# in depth又快速的看了一遍，挺多收获；Functional Programming in Scala Specialization系列，已经学完了三个，这个真是赞，课程好，习题布置的更好；SICP抛弃了第二章最后一点点内容，进入第三章，中间断了太久，进入新的篇章，能让人学下去，算是一个策略吧。
Scala系列全部五个课程都完成，分布式和SICP能有些进展，Calculus With Analytic Geometry 2nd edition在时间充裕或者不想学习其他内容的时候，也可以看看。

数学，MIT 18.01就快要结束了，今年计划是18.02和18.06。

英语，单词几乎在天天背；按照计划，NEC2也学习到了70课，同时，完成了Unit 1的习题部分；其余时间，学习了公司的GlobalEnglish，到了第三单元，进度基本都略有提前，主因是目前level低，学习的比预计的快。
下个季度，NEC2应该完成，同时，NEC3前十课；NEC2 Unit 2习题应该能搞定；GE搞定Level3没问题，Level4能到完成一半？尽量吧。

C# 6.0发布很多小功能，帮助开发者提高生产力。

整体来说，这些功能让我们编写的代码更简洁，也更具可读性。了解这些功能，工作效率会更高，写的代码的可读性更好，能够更好的专注于实现自己想要的功能，而不是其他的什么东西。

自动属性的增强

只读属性
其实C#里面的自动属性已经很好用了，简洁，提供多样的访问性控制。
不过长久以来，我们申明只读属性本质上都不是只读的，因为类内部可以修改，只是对于使用者来说是只读的。

1
2

public string FirstName { get; private set; }
public string LastName { get; private set; }

新的版本提供了真正意义上的只读属性：

1
2

public string FirstName { get; }
public string LastName { get; }

你只能在构造函数里面赋值，其他地方赋值都会编译错误。

自动属性初始化
这个很简单，就像是这样：

1

public ICollection<double> Grades { get; } = new List<double>();

只会被初始化一次，这样就没有必要在构造函数里面写一遍了，对于有些开发者，构造函数不会重载使用，那样子可以少写很多次。

Expression bodied函数
如果一个函数只有一行，不用大括号括起来了，直接=>就可以了。

1
2

public override string ToString() => $"{LastName}, {FirstName}";
public string FullName => $"{FirstName} {LastName}";

第一个是重载了以函数；第二个是只读属性，同样好用。

using static
这个feature让我们写代码的时候能少敲几个字母吗？估计不行，因为反正有智能提示。
好处是让代码更简洁一些。

1
2
3

using static System.String;
if (IsNullOrWhiteSpace(lastName))
    throw new ArgumentException(message: "Cannot be blank", paramName: nameof(lastName));

?. Null条件操作符
这个挺好用的，先判断前面的对象是否是空，如果是null，就不进行后面的操作。对于event的调用，很好用，因为最常用的pattern就是先看event是不是null，不是null的话Invoke。

1
2
3
4
5

var handler = this.SomethingHappened;
if (handler != null)
    handler(this, eventArgs);

this.SomethingHappened?.Invoke(this, eventArgs);

现在只需要一行就搞定了。对于某些公司要求if必须有大括号（我个人也喜欢打）的话，能省掉更多的行数。

String interpolation
这个在前面的代码里面出现了，比如FullName这个只读属性，以前要这么写：

1
2
3
4
5
6
7

public string FullName
{
    get
    {
        return string.Format("{0} {1}", FirstName, LastName);
    }
}

现在只需要一行就能搞定。
这个里面可以写很复杂的表达式，调用函数等等。
我个人觉得，打日志拼接字符串的时候很有用，以前string.Format里面{}能高达十个以上的参数，都跟在后面，鬼知道哪个对应数字编号几，有了这个feature，可读性大大提高了。

异常过滤
个人感觉是一个简化代码的小feature，相比C# 7.0而言，提高并不是太多，这里就不举例子了。

nameof
超级有用的feature。
以前写MVVM SDK的时候，太多地方会用PropertyChangedEventArgs，写一个string，有的时候变量名换了，这里忘记换了，导致运行结果不正确，debug半天，有了这个功能，直接rename重构，就能全部换掉了。
还有就是抛异常的时候，需要写入参变量名，这样子就能自动rename而不用自己修改了。

Index Initializers
以前List这种集合可以方便的再后面{}初始化，现在Dictionary也可以了。

1
2
3
4
5
6

private Dictionary<int, string> webErrors = new Dictionary<int, string>
{
    [404] = "Page not Found",
    [302] = "Page moved, but left a forwarding address.",
    [500] = "The web server can't come out to play today."
};

新版本还提供了通过扩展Add方法，使得自定义的集合类也可以使用类似的初始化语法。

2017-09-07 更新
部署在虚拟机上的博客（用WordPress搭建的）被盗，导致这篇文章无法恢复了。
从MS Library借了这本书，又看了一遍，还做了挺多3星4星的问题。
这里是一些solutions

题目链接

这道题乍一看是位运算，其实是一道和概率分布相关的题目。

有y0 y1 y2一系列32bits的无符号数
x初始为0，然后和这一系列数异或操作，操作了N次，直到x是2^32-1，其实就是x所有bits都是1。
求N的期望值。

期望怎么计算呢？
计算对于每一个n对应的概率p(n)，然后加权求和。
我们现在逐一分析一下
N为1，那么说明y0每一个bits都是1，概率是1/(2^32)
N为2，针对每个bit进行计算，第一个bit，结果是1的概率是1减去不是1的概率，不是1的概率就是y0的第一bit不是0，y1的第一bit也不是0，概率是1/(2^2)，那么p(2)=(1-1/(2^2))^32 - p(1)
N为3，p(3)=(1-1/(2^3))^32 - p(1) - p(2)
以此类推
题目要求小数点后十位，如果p(n)很小，乘以n对结果都没有影响了，也就是p(n)*n小于10的十次方。

我计算的时候搞了一个数据结构保存概率的分子和分母。我解答出来之后，看了下别人的分析，感觉直接使用double 来保存概率也能给出正确答案，我没有试，不确定。
下面是我的代码：

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

public class Probability
{
    public BigInteger Numerator { get; set; }
    public BigInteger Denominator { get; set; }

    public Probability(BigInteger numerator, BigInteger denominator)
    {
        Numerator = numerator;
        Denominator = denominator;
    }
}

public static string GetAnswer()
{
    List<Probability> probabilities = new List<Probability>();
    probabilities.Add(new Probability(0, 1));
    BigInteger twoPow32 = BigInteger.Pow(2, 32);
    for (int i = 1; ; i++)
    {
        BigInteger baseDenominator = BigInteger.Pow(2, i);
        BigInteger baseNumerator = baseDenominator - 1;
        BigInteger lastBaseDenominator = BigInteger.Pow(2, i - 1);
        BigInteger lastBaseNumerator = lastBaseDenominator - 1;
        BigInteger denominator = BigInteger.Pow(baseDenominator, 32);
        BigInteger numerator = BigInteger.Pow(baseNumerator, 32);
        BigInteger lastNumerator = BigInteger.Pow(lastBaseNumerator, 32);
        probabilities.Add(new Probability(
            numerator - lastNumerator * twoPow32,
            denominator));

        if (probabilities[i].Denominator / probabilities[i].Numerator / i > BigInteger.Pow(10, 12))
        {
            break;
        }
    }

    BigInteger ansDenominator = probabilities.Last().Denominator;
    BigInteger ansNumerator = 0;
    for (int i = 1; i < probabilities.Count; i++)
    {
        Probability current = probabilities[i];
        BigInteger times = ansDenominator / current.Denominator;
        ansNumerator += times * current.Numerator * i;
    }

    BigInteger times11 = ansNumerator * 100000000000 / ansDenominator;
    double answer = (double)times11 / 100000000000;
    return answer.ToString("N10");
}

又有一个月没有写过东西了。

虽然在过去的一个月，看了些书，学习了很多东西，包括学车，但是都没有花时间总结成文字。比如很久之前做过的欧拉项目的题目，至今写没有整理思路和代码；很久之前读的书，至今也没有整理当时读的想法；很多很多想做的事情，都没有完成。

应该也不是懒，因为做了很多事情，为什么没有写呢？很简单，把这个事情的优先级放的比较低。

读书做笔记，思考的事情写下来，都是对自己认识的再整理，是很有好处的，是否真的理解，写不出来就是没理解，是否真的想明白了，写不出来就是逻辑没有理清。

所以，合理分配时间，该整理的整理，该写的写，该记的记，不能一味的往前跑，也应该适时停下来回顾过去。

人的精力总是有限的。

又想一本一本的刷计算机的经典书籍，又想一点一点的啃数学，还想着兼顾物理学和经济学的基础，最后，还想着好好学习英语。考虑第一句，怎么可能都做呢？即使都做，能做好吗？

精力的第一个层面，时间。看计算机的时间多一点，那么看数学的时间就会少一点，思考物理的时间多一点，遐想算法的时间就会少一点，练习听力的时间多一点，训练思维的时间就会少一点。上帝很公平的，每个人每天只有24个小时。
面对第一个问题，时间不够用。从三个方面解决。舍。想想自己到底想到的东西，把经济学进阶的书和公开课从自己的TODO LIST里面删除掉，看看科普级别的或者入门级别的，就好了。效率，提高效率，个人觉得从睡觉时间、从锻炼身体的时间里面省出来一点学习是不对的，因为睡眠、健身也是很重要的事情，不亚于学习。改进现有的做事的方式或者安排，提高效率。优先级。应该给自己排一个优先级，每个方面投入多少时间，先做什么，再做什么，分清主次。比如，计算机和英语优先级高，博览群书的优先级相对而言低一些。

精力的第二个层面，身体，精神。身体好的时候，应该尽可能的利用时间进行学习，反之，身体难受，应该尽快休息，尽快恢复到好的状态。精神状态也是类似的。之前的有些做法，身体不适或者精神状态不好，为了学习而学习，效率不高，学习的效果也不好。

学习这件事本身，也应该多总结。以前，我总认为人生是一场马拉松，很多人都说不要输在起点，可是事实是不同人的起点本就不一样，或许已经输在了起点，我们应该坚持不懈的努力进步。而我现在觉得，人生或许是一场场的短道冲刺组成的，当然，对于起点不同这件事，我的看法没有变，输在起点不可怕，可怕的是自己不努力，最后仍旧输在终点，哪怕少输一点，或者达成自己的目标也好啊。接着扯短道冲刺，精力这玩意可能也是循环往复的，充沛的学习，用的差不多了，想办法冲一点，恢复精力，再学习，以此循环。所以，在处于学习低估的时候，要想想是不是精力用没了，适当的减速，恢复精力，再努力冲刺。
工作时间不长，3年半，观察了很多人的事业发展，有大神级别的快速晋级，但是，多数的人都是普通人，遇到事业的发展期，比如有前途的项目，给力的老板，天时地利人和等等，抓住机会，努把力，冲刺一下，上升一个台阶，有的时候呢，为了寻找这么好的条件，转战个两处，发现两年过去了，什么也没有做成，也是有的。感觉这和我说的人生是短道冲刺有点类似吧，不过冲刺完了，可能有的时候也没能抓住机会，上升一个台阶，别气馁，找一找，还是会有这样子的机会的。不过话说回来，能抓住机会的，往往是能力不错，在平常时有所积累的人。

啰七八嗦一大堆，其实就是思考了下当下和长远的规划，调整了一下前进的方式，就是这样。

题目的原始链接

定义s(n) = m，给定一个整数n，m是最小的整数，使得m!能够整除n。
举两个简单的例子，s(10)=5，s(25)=10。
定义S(n) = ∑s(i) 2 ≤ i ≤ n
题目中给了一个当n = 100的值用于测试：S(100)=2012

求S(10^8)

首先要意识到，不可能把阶乘本身算出来，比如1517，由质数37和41相乘得到，那么对应的m应该是41，但是41的阶乘非常之大。
给定一个数n，求满足题意的m，因为这里肯定需要遍历所有的n，10 ^ 8这么大了，所以求m的函数的时间复杂度最好是常量时间，nlg(n)也很快，n * sqrt(n)就太慢了，这都到10 ^ 12次了，复杂度已经高的吓人了，计算机真心无法短时间算出来了，所以我们下面的目标就是在合理的时间复杂搞定s(n)这个函数：一定要控制在nlg(n)以内。
首先，如果这个数n是质数，那么m肯定就是n本身。
对于一个非质数，一个可行的思路就是把n分解质因数，质因数出现的次数也是需要保留的，要不然25这个数，是5*5，如果不保留质因数的次数，那么计算得到的m就成了5了，显然是不对的。然后再如何处理呢？
假设分解质因数结果是p1 ^ n1 * p2 ^ n2 * … * pq^ nq
想办法凑够n1个p1，p1包含1个p1，2*p1又包含一个（如果p1等于2，这里还会多包含一个），3*p1又包含一个p1，依次类推。
再想办法凑够n2个p2。
依此类推。
共计q个结果，最大的那个数字就是我们要求的m。

以上想法计算S(100)没啥问题。但是：虽然我把之前分解质因数的函数性能提高了好几倍，但是离nlg(n)还是差很远，所以导致短时间无法运算完毕。。。

如果我能过滤掉很多值不用去计算了，那么时间就能大大降低了。
首先10 ^ 8以内的质数占了5.7%的样子，所以这5.7%是不用计算的。
其次，考虑某个质数p，乘以小于它的某个数m，得到的这个值n，S(n)也是p。写一个两层for循环就能得出这些n值，这占了大概66.7%，这一下子就节省了大多数的时间。
再次，在上一条的基础上再进一步，某个质数p，乘以两个小于它的数m1和m2，得到的n值，S(n)也是p。三层for循环能搞定，这大概占了22.3%，又能节约挺多时间的了。
这里可以做一个小的优化，m2可以从m1+1和p/m1+1两者比较大的一方开始，因为如果m2*m1小于p，那么这个数字肯定在上一步的时候就被标记了。优化之后，三层for循环，用时不到2s。
再再次，还能再排除3.4%的数据，这里也可以使用上面提到的优化思想。
最后，只剩约1.9%的数据需要按照之前说的逻辑进行判定了。

生成1亿以内的质数用时约3.9s，中间若干步耗时约5s，最后处理1.9%的数据耗时10s。。。
其实沿着中间那一段优化的想法，可能可以在线性时间复杂度做完，但是想了半天，没有太好的想法，暂时就这样子吧。

下面是我写的代码：
话说这次代码又丑又长，特别是中间的几个for循环嵌套。。。

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154

public static long GetAnswer()
{
    var primes = Utils.GenPrimes(N);

    var result = new long[N + 1];
    foreach (var p in primes)
    {
        result[p] = p;
    }

    for (int index = 0; primes[index] < N / 2; index++)
    {
        for (int j = 2; j < primes[index]; j++)
        {
            var tmp = j * primes[index];
            if (tmp > N)
            {
                break;
            }
            else
            {
                result[tmp] = primes[index];
            }
        }
    }

    for (int index = 0; primes[index] < N / 6; index++)
    {
        for (int j = 2; j < primes[index] - 1; j++)
        {
            long k = Math.Max(j + 1, primes[index] / j);
            var test = j * k * primes[index];
            if (test < 0 || test > N)
            {
                break;
            }

            for (; k < primes[index]; k++)
            {
                var tmp = j * k * primes[index];
                if (tmp < 0 || tmp > N)
                {
                    break;
                }
                else
                {
                    result[tmp] = primes[index];
                }
            }

        }
    }

    for (int index = 0; primes[index] < N / 24; index++)
    {
        for (int j = 2; j < primes[index] - 2; j++)
        {
            long k = Math.Max(j + 1, primes[index] / j);
            var test = j * k * (k + 1) * primes[index];
            if (test < 0 || test > N)
            {
                break;
            }

            for (; k < primes[index] - 1; k++)
            {
                long m = Math.Max(k + 1, primes[index] * primes[index] / (j * k));
                var test2 = j * k * m * primes[index];
                if (test2 < 0 || test2 > N)
                {
                    break;
                }

                for (; m < primes[index]; m++)
                {
                    var tmp = j * k * m * primes[index];
                    if (tmp < 0 || tmp > N)
                    {
                        break;
                    }
                    else
                    {
                        result[tmp] = primes[index];
                    }
                }
            }
        }
    }

    for (int i = 2; i <= N; i++)
    {
        if (result[i] == 0)
        {
            var facs = Utils.TrialDivisioFac(i, primes);
            var maps = GetFactorsCounts(facs);
            long m = long.MinValue;
            foreach (var map in maps)
            {
                var temp = GetMaxMByPrime(map);
                if (temp > m)
                {
                    m = temp;
                }
            }

            result[i] = m;
        }
    }

    return result.Sum();
}

private static long GetMaxMByPrime(KeyValuePair<long, int> map)
{
    long result = 0;
    long count = map.Value;
    while (count > 0)
    {
        result += map.Key;
        long cur = result;
        while (cur > 0)
        {
            if (cur % map.Key == 0)
            {
                cur /= map.Key;
                count--;
            }
            else
            {
                break;
            }
        }
    }

    return result;
}

private static Dictionary<long, int> GetFactorsCounts(List<long> facs)
{
    var maps = new Dictionary<long, int>();
    foreach (var fac in facs)
    {
        if (maps.ContainsKey(fac))
        {
            maps[fac]++;
        }
        else
        {
            maps[fac] = 1;
        }
    }

    return maps;
}

开篇第一章，讲了老师应该如何教学，如何适当的提示学生，这是一件非常困难的事情，在我学生时代，也有过类似的经历，提示的太多，一下子有了思路或者解决方案，导致自己在思维上没有太多的训练了，提示的太少，又和没有提示有太多的区别。不过这个作者当老师很多年，很有心得，知道如何把握这个度，在后续的章节，基本都是按照这种循序渐进的方式讲述，挺好的。
书中阐述了很多的方法，结合书中给出的示例，解释的很清晰。其实很多方法我们平时，或者说在以前的学习工作中，无意识的使用过，只是没有使用文字描述出来罢了。比如有时候思考欧拉题目的时候，把问题分解再重组，有的时候迷失在一个点的时候要想到是不是还有条件没有用上，又或者是往等价的问题上去考虑等等，这些想法在本书中都详细的阐述，更精准更具象，而不是直觉上的。
作者也阐述了很多其他的方法论，也都挺实用的，但是美中不足的是，有的示例题目本身并没有解决就结束了：他只阐述到能够表明作者方法的地方就完事了，可以理解，毕竟，作者是要用示例来阐述他的方法论而不是具体的题目本身，但是，没有解完导致我要去想一想，很多还搞不定，费时又打击人，哎，还需要加强数学方面的学习啊。
说中说了一个概念，叫做完美描述的题目，题中的题设对于解题来说都是必要的，即没有多余的条件，并且是完全充分的，即不缺少条件，最后，条件中没有相互矛盾。这样的题目才适用于他说的一些方法，比如检验和思考过程时要考虑题目条件都用到了吗。其实，我们学生时代做的多数题目都是这样的题目，所以一般情况下，不用去质疑题目本身。
画图是一种很好的解题的方式，不仅仅可以用于几何题，非几何题也通过画图来给自己更多的灵感。不过画图也是一门学问，个人觉得，首先，如果题目没有特殊要求的话，画的图形最好也更一般比较好，不要故意画出等腰三角形，两条线段一样长之类的，可能会给人误导，其次呢，如果能真实等比例最好，如果需要借助太多工具才能真实，这样可能会很费时，还是直接画比较好，需要注意的是，尽可能的真实的反映题目，因为图形本身可以给我们灵感，最后，使用不同的线或者类似的区别物来以示区别，看起来更清楚一些，比如实线虚线表示不同的作用。
如果遇到了一道你不会的题目，别人失败的挫折感一直折磨你，换一道类似的较为容易的题目去做，这可能会给你启发，还会调动出可能需要的知识，还能帮你建立解决问题的信心。
变化题目这件事情，几乎贯穿我们解题的过程，除非是一道非常容易非常直接的题目。我们不管的观察未知量，把题目分解重组，使用了诸如普遍化、特殊化、类比等等的思想，都是为了解题，有时，我们还会利用引入辅助元素——辅助题目这些方法来解题。
探索法也是很重要的，特别是在某些关键点，我们可能会先猜测某个结论，然后继续证明下去，但是这种猜测并不能替代严格的证明，回过头我们还是必须证明我们猜测是否正确。
书中作者不止一次提到，他所阐述的方法，是一种普世的方法论，不限于解决数学题，在日常中遇到的问题，也可以使用这些方法去解决。比如类比，我在理解一个新的计算机概念的时候，经常类比成一个已知的概念，很多作者写书也是这么做的。
归谬法小节，一个很有意思的题目，0到9十个数字，只能使用一次，组成的若干个数字，和为100。最后使用归谬法，证明这是不可能的（另外一个可能的直接证明是舍九法）。间接证明，小时候说的反证法，也举了一个很有意思的题目，质数是无穷个。假设质数有限多，最大的是P，那么Q = 2 * 3 * 5 *…* P + 1，除以假定的现有的质数，都剩余1，那么在假定条件下，Q是质数，且比P大，那么假定不成立，反面，即质数是无穷多个，成立。
教学的两条规则，第一是教什么，第二是你知道的应该比你想要教的东西多。拿出这一条，是想说，教别人某种东西，会更好的提供自己在这个领域的积累，只少能够把现有的东西熟悉到不能再熟悉，真正的做到融会贯通。
此书最后一个部分包含了20道题目，基本上属于高中竞赛或者初中竞赛的的难度，或者更低一点，不过选题的角度都非常好，都很具有代表性，而且题目也尽可能的覆盖多个主题，有几何，有代数，有递归，有证明。

用书里的某句话结束，灵感，是神的恩赐，你必须努力工作，或者至少有强烈的愿望，才配得到这样的恩赐。加油！

有一道非常经典的题目，一只熊从P点出发，向正南走一公里，然后左转向正东走一公里，然后再向正北走一公里，此时正好回到了P点，问熊是什么颜色的。

很多人都知道答案，是白色的，因为P点是北极那一点，所以熊是白色的。

但是只有北极这一点符合题目要求吗？
显然不是的，还有很多很多的点都符合。
在离南极点很近的一个圈（纬度圈1），往北一公里的一个稍大点的圈（纬度圈2）上所有的点都是符合题意的。在纬度圈2上找一点P，往南走一公里，达到纬度圈1上的某点Q，向正东走，就是沿着纬度圈2走，一公里，可以是一圈也可以是多圈，然后回到Q点，向正北走一公里，也可以回到P点。
由于纬度圈2可能性有n种，那么纬度圈1可能性也有n种，显然，符合题目的P点也是无限多的。

虽然可能的点无限多，但是其余那些点都在南极附近，不会有熊出没的。

原题链接

这个题目比较长，下面简单描述一下。

有一个数字表，显示数字的方式可以看原题，其实是老式计算器那个样子，也像小时候做的奥数题，拿火柴棍摆正正方方的数字。
给它一个输入，比如说137，首先它会显示137，然后计算137各个数字之和，得到11，然后显式11，再计算得到2，显示2。

显示数字或者是不显示，都需要一次转换，比如显示4，要4次转换，比如显示8然后什么都不显示，需要7次转换。

Sam的表显示的方式很直接：
比如输入137，显示137，再关掉，一共需要(2 + 5 + 4) × 2 = 22次转换，137各个数字之和是11，显示11再关掉，(2 + 2) × 2 = 8次转换，最后的数字2，需要(5) × 2 = 10次转换。一共需要40次转换。

Max的表稍微智能一点：
比如137变成11的时候，3和1是有公共部分的，7和1也是有公共部分的，那么在关掉137的时候，对应下个数字的地方就不关掉了，显示下一个数字的时候就不需要再打开，用此方法较少转换的次数。
打开137，2 + 5 + 4 = 11次转换，关掉的时候，11的那4个地方不关闭，那么关闭需要7次转换；显示11不需要打开了，关闭11显示2，第二个1的右上角那一个也不要关闭，所以关闭11需要3次转换，打开2，只需要4次转换而不是5次，关闭2需要5次转换。总共需要30次转换。
相比Sam的少了10次。

题目的输入是10 ^ 7 和 2 * 10 ^ 7之间的所有质数，求省下来的转换次数。

其实这个题目看似很难，如果找对了关键点，其实很简单。
所谓省下来的次数，就是2个数字直接重叠的那一部分，比如0和8重叠就是整个0，6条边，2和4就重叠了两条边。
于是乎，我写了一个二维数组表示任意两个数字之间的重叠个数。

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

private static int[,] Overlap = new int[10, 10]
{
    { 6,2,4,4,3,4,5,4,6,5},
    { 2,2,1,2,2,1,1,2,2,2},
    { 4,1,5,4,2,3,4,2,5,4},
    { 4,2,4,5,3,4,4,3,5,5},
    { 3,2,2,3,4,3,3,3,4,4},
    { 4,1,3,4,3,5,5,3,5,5},
    { 5,1,4,4,3,5,6,3,6,5},
    { 4,2,2,3,3,3,3,4,4,4},
    { 6,2,5,5,4,5,6,4,7,6},
    { 5,2,4,5,4,5,5,4,6,6}
};

万一人为计算的时候搞错了呢？我又搞了个函数检查一下，我把数字的边从上到下，从左到右编号。比如数字1的两条边就是3,6，数字7的边就是1,2,3,6。然后计算数字的重叠部分，看看和我手写的矩阵是否一致。我第一遍运算的时候，还真发现矩阵里面的一个错误。

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

private static void Check()
{
    var digital = new List<List<int>>();
    digital.Add(new List<int>() { 1, 2, 3, 5, 6, 7 });
    digital.Add(new List<int>() { 3, 6 });
    digital.Add(new List<int>() { 1, 3, 4, 5, 7 });
    digital.Add(new List<int>() { 1, 3, 4, 6, 7 });
    digital.Add(new List<int>() { 2, 3, 4, 6 });
    digital.Add(new List<int>() { 1, 2, 4, 6, 7 });
    digital.Add(new List<int>() { 1, 2, 4, 5, 6, 7 });
    digital.Add(new List<int>() { 1, 2, 3, 6 });
    digital.Add(new List<int>() { 1, 2, 3, 4, 5, 6, 7 });
    digital.Add(new List<int>() { 1, 2, 3, 4, 6, 7 });
    for (int i = 0; i < 10; i++)
    {
        for (int j = 0; j < 10; j++)
        {
            int overlap = digital[i].Intersect(digital[j]).Count();
            if (overlap != Overlap[i, j])
            {
                Console.WriteLine(i + "\t" + j + "\t" + overlap);
            }
        }
    }
}

接着往下想，给两个数字，比如137和11，如何得到重叠部分呢？很简单，从最后一位开始比就可以了，最后一位的两个数字，去查矩阵，很容易得到重叠的值，然后再考察倒数第二位。。。代码如下：

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

private static int GetCount(int num1, int num2)
{
    int count = 0;

    while (num1 > 0 && num2 > 0)
    {
        count += Overlap[num1 % 10, num2 % 10];
        num1 /= 10;
        num2 /= 10;
    }

    return count;
}

能够比较两个数字了，那么给定要给输入，一个几百万大的质数，求各个数字之后，对比两个数字之间的重叠值，然后再计算数字之和的数字之和，再对比重叠值，循环到个位数即可。

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

private static int GetCount(int p)
{
    int count = 0;
    while (p >= 10)
    {
        int sum = p.ToString().Select(c => c-'0').Sum();
        count += GetCount(p, sum);
        p = sum;
    }

    return count * 2;
}

为什么要乘以2呢？因为从第一个数字过渡到第二个数字，比如11到2，重叠部分是1，关闭11的时候可以少关闭1，显示2的时候又可以少打开1，所有要乘以2。

万事俱备，最后，拿到10 ^ 7 和 2 * 10 ^ 7之间的所有质数，遍历求和即可。

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

public static int GetAnswer()
{
    Check();

    int count = 0;
    var primes = Utils.GenPrimes(20000000).Where(p => p > 10000000);

    foreach (var p in primes)
    {
        count += GetCount((int)p);
    }

    return count;
}