接触数论已接近半年,回想昔日在HDU老菜鸟杯上出的那2道数论题，从那时开始到现在几乎都在啃数论,现在或许应该是停止啃的时候了,毕竟ACM比赛不仅仅是只有数论.走过了这半年，下面稍微做一个小结吧！
这里的小结只涉及到算法，并未设计到具体的代码实现,有兴趣的朋友可以在我的空间找到大部分代码.
作为数论，实际上正如某位大牛称的"素论",大部分是围绕素数来展开，当时学长教我的素数筛选法,第一次认识到了数字的美妙.
1.素数的筛选
1-1.关于简单素数筛选的问题，我推荐下面这道:
http://acm.fzu.edu.cn/problem.php?pid=1607
这里我不给出题目的大意了,需要注意的一点:素数筛选一般都只是一个辅助的算法,而对于一般的题目来说,筛选的级别最多是几百万,用线性的筛法完全足够,当然如果你要优化完全可以使用2倍压缩的筛法,这里就不介绍了.
于是筛选完素数以后，这题的做法就不难想到了.
对n分解素因子,然后就可以得到n的因子数.注意这里求因子数用到了组合数学的一些知识,可以作为一个小结论记忆起来.答案就是所有素因子个数加上1以后拿去乘起来的结果.
1-2.下面这题也用到了素数筛选(素数筛选实在太常用了,这里只给比较经典的题目)
http://acm.fzu.edu.cn/problem.php?pid=1753
题目大意也不再说明了，这里需要注意的是你必须知道如何对n!进行素因子分解
1-3.至于筛选素数的目的，无非就是
a.真的是为了得到某范围内素数
b.对求数字的因子加速,即任何的n的素因子Pi都有Pi|n,这是显然的.于是可以利用这个特点，在得到素因子的种类和个数以后采取枚举的做法来得到所有的因子(一般用dfs递归实现)
2.素数判断
这个问题比较难办,因为各种算法的复杂度不一.
a.暴力O(sqrt(n))
b.米勒素数测试
c.预先打表判断
其中一般是用a,c.而b实在有点太"数学"了,代码写起来也确实不短,它是基于概率的算法,一定要注意实验次数(根据经验，实验次数在2以上效果比较好),同时这个是建立在你已经会二分求幂的前提下.
而一般的题目很少用到b.不过在用到随机分解素因子的算法时需要使用b.这里就不具体介绍了
3.模方程问题
模方程是由扩展欧奇里德来展开的.
我们知道
ax + by = gcd(a,b)是可以在log级别的时间内计算得到的.
于是我们变形
ax=gcd(a,b) (mod b)
于是模方程就这么出来了.
对于模方程:ax=b(mod n)
a.解存在的条件:gcd(a,n)|b
b.解个数:gcd(a,n)
c.解范围:[0,n-1]
模方程一般比较常见，也经常组合其他算法，比如求指标,求解模方程组等.
下面这题就是相当裸的模方程:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1061
而如果比赛中只是这么一个方程模型显然是不难的,可是如果加上了解的范围可就不那么简单了:
http://acm.sgu.ru/problem.php?contest=0&problem=106
注意一点,这里涉及到了一个看起来MS很麻烦的问题,即负数在mod系统下如何表示:
对于C++，可以这么处理
int MOD(int a,int b)//return a%b
{
a%=b;
return a<0?a+b:a;
}
即-5%7=2,-3%9=6..这种方法在某些题目中还是需要用到的
4.模方程组问题
看到这里，大部分人可能首先想到的就是中国剩余定理,显然网络上可以找到不少其现成的代码，其原理也不难,可是由于中国剩余定理来解模方程对于模的数有很大的限制，即他们必须是互素的.这里就比较尴尬,因为满足这种情况的方程在现实条件下还是不多的,大部分是不互质的.
不过这里先介绍中国剩余定理的一些用法吧
解赤裸裸的模方程组是没问题,直接套套就可以解决:
http://acm.fjnu.edu.cn/show?problem_id=2034
http://acm.fzu.edu.cn/problem.php?pid=1402
可是如果遇到了不是互素数的如何处理呢?其实不难，大家推推看.其实就是基于最基本的定义.
至于例题PKU是有的，不过我忘记题号了..大家可以直接去上面的地址提交1402.
5.高次方程问题
a^x = b(mod c)
看起来十分平常可爱的方程其实蕴藏了无限的奥秘
1.知道a,x,c求b,这个分了很多情况，具体参考我以前的帖(100%有解)
2.知道a,b,c,求x (有可能无解)
3.知道x,b,c,求a(依然有可能无解)
4.知道a,x,c,求某区间范围内的c(持续有可能无解)
从1到4，求解的难度是越来越大的.
这里只是给出思路:
1.二分求幂
2.Baby-step+Hash
3.求原根+求指标+Baby-step+Hash+解模方程+欧拉函数+...(PS,c 必须是素数)
4.(a^x-b) 在区间内的因子，无解-_-dddd(至少我不会,因为x可以很大...)
上面的数字范围一般都很和谐的<2^31
而对于1.x可以超大,比如10^1000000:
http://acm.fzu.edu.cn/problem.php?pid=1759
下面给出2的例子:
http://acm.hdu.edu.cn/showproblem.php?pid=2815
下面给出几个高次方程的综合题:
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3538
http://202.120.80.191/problem.php?problemid=2700
http://acm.sgu.ru/problem.php?contest=0&problem=261
6.循环节,循环循环~
a.fibonacci数列的性质
f(a^b) %c 的循环节开始位置居然都是1(神奇..)
http://acm.hdu.edu.cn/showproblem.php?pid=2814
b.高次方程在mod系统下的指数循环.
这里不加证明的给出一个结论:
循环节的开始位置不都一定从1开始,并在某些范围内循环节开始位置都不大.
7.数论和其他算法混合起来用
如下:组合数学中的卡特兰数利用到了数论
http://acm.fzu.edu.cn/problem.php?pid=1775
组合数学中的BurnSide，计算同构的时候利用到数论
http://acm.fzu.edu.cn/problem.php?pid=1796
组合数学中组合数求mod利用到数论
http://acm.fzu.edu.cn/problem.php?pid=1833
8.暂时写到这了.