简单数论 李富数论l简而言之 ,数论是研究整数的理论l在 ACM竞赛中 ,经常用到数论的相关知识l纯 数论的题目不多 ,大部分是和其他类型的问题结合起来的l约数 ,倍数 ,模线性方程 ,欧拉定理 ,素数内容1.初等数论的概念2.求素数的方法3.最大公约数4.欧拉函数5.模线性方程6.中国剩余定理7.唯一 因子分解8.其他1.初等数论的概念整除性和约数：l假设 d和 a是整数， d|a（读作 d整除 a），意味着存在某个整数k，有 a=kd。l如果 d|a，并且 d0 ，则称 d是 a的约数。l每个整数 a都可以被其平凡约数 1和 a整除， a的非平凡约数也称为 a的因子 。1.初等数论的概念素数和合数l对于某个整数 a1，如果它仅有平凡约数 1和 a则称 p是素数。否则 p是合数。l可以证明素数有无限多个。l筛法求素数。1.初等数论的概念除法 定理 in;+i)for(j=0;jm +j)如果 pj整除 i，则 i不是素数如果都不能整除，则 i是素数，添加到素数列表 pN;缺陷：时间复杂度太高2.求素数的方法筛法求 1n所有素数l初始时容器内为 2到 n的所有 数l取出 最小的数 p,p一定是质数 ,删去 p的所有倍数 (注 :只需从 p2开始删除即可 )l重复 上述步骤直到容器为空l用 bool数组实现即可缺陷 :一个数可能被重复删去多次 ,影响效率
