基础算法与数据结构（十五） 数学

这个话题实在很宽泛，本人水平难以企及。但是最近一年，深感数学之于计算机学科的重要性。聊列此提纲，便于查阅和学习。前人之述备矣，网络可以解决一切。

数论部分

数论的题目，感觉看着基础概念有的小学就学过，但做题也能很难，而且完全想不到的感觉。。。

就列几个名称吧

整除性和约数、素数和合数 除法定理（对于任何整数a和任何正整数n，存在唯一整数q和r，满足0<=r<n且a=qn*r ) 余数和等模 公约数与最大公约数 欧几里得算法：利用GCD递归定理（GCD(A,B) = GCD(B.A MOD B) ) 扩展的欧几里得算法： 可以计算出d = gcd(a,b) = ax+by中的x,y可以为0或负数 互质性 唯一因子分解定理（合数a只能用唯一方式分解成若干个素数相乘的形式）

欧拉函数 欧拉常数

求解模线性方程

中国余数定理

利用反复平方法求幂（快速求a^b mod n，防止爆范围）

题目

帖一道Google在Kickstart2017 Round A的题目吧，感觉对数学的要求很高。（翻墙必须）

Dashboard - Kickstart Round A 2017 - Google Code Jam

主要问题就是求n*m的点阵中，可以得到多少个正方形？

这个问题在zhihu上有数学相关的讨论，在一些个人blog中有具体解法和另一些可行的想法。

https://www.zhihu.com/question/56657137

概率论

概率论其实对计算机科学来说也是一门十分重要的课，现在十分火热的人工智能和概率论密不可分，以及还有经典算法中的模拟退火也和概率论有关。

好好学好概率吧，无论是古典概率和一些需要使用微积分的概率计算方式，虽然当下可能没有什么用，但这真的是内功啊。

具体数学/离散数学

这两个应该是和计算机关系最大的数学分支了，两个都有经典的教材可以参考，一本是具体数学，一本是离散数学概念及其应用。都是两本大部头，有空的时候可以翻翻，有时真的会幡然醒悟，原来这个可以用数学更好的完成。

数学真的是一个很重要的东西，希望每个人都能学好数学，不要有抵触情趣。

TAOCP也是巨著，可以参考，全是数学内容，看完这个应该真的就是大神了吧。

以上。

这是本系列所有的内容。有些详细，有些划水，总而言之， 一直以来的支持表示感谢！ 今まで、 ありがとございました！

完结于 2017.5.9