Question

计算数论和初等数论的区别

Answer 1

筛法求素数，
欧几里得算法，
扩展欧几里得算法，
快速幂（矩阵快速幂，整数快速幂），
a*b%n（都是LL范围），
欧拉函数（不超过n且与n互素的那个），
乘法逆元，
确定性的严格素性检测，
拟素数测试（Miller-Rabin，Pollard_Rho），
整数分解质因数，
中国剩余定理，
模线性方程，
离散对数（Shank's Baby-Step-Giant-Step Algorithm）
矩阵的离散对数，
组合数取模（Lucas定理），
平方剩余，
高次同余方程（原根），
超高次整数幂取模（http://www.zhihu.com/question/20397628）。
其实还有蛮多的，不好划分到数论这一块，比如母函数的应用，整数的拆分，求解线性递推方程。如果划分到数论总感觉怪怪的，但是不划到数论又感觉怪怪的。直到我想起了大学的一门专业选修课，“组合数学与数论”。