文档介绍：1 ACM 数论 ?cid=6#overview 2初等数论的概念整除性和约数: 假设 d和a是整数, d| a (读作 d整除 a), 意味着存在某个整数 k,有 a=kd 。如果 d| a ,并且 d≥0,则称 d是a的约数。每个整数 a都可以被其平凡约数 1和a整除, a的非平凡约数也称为 a的因子。 3初等数论的概念素数和合数对于某个整数 a>1 ,如果它仅有平凡约数1和a则称 p是素数。否则 p是合数。可以证明素数有无限多个。筛法求素数。 4求素数方法1) p[N] 存储所有的素数,二重循环, 用已经求出的不大于平方根的所有素数试除 for(i=2;i<n;++i) for(j=0;j<m && p[j] * p[j]<= i ;++j) 如果 p[j] 整除 i,则 i不是素数如果都不能整除,则 i是素数,添加到素数列表 p[N]; (m++) 5 2)给定一个范围(求这个范围内的素数),进行如下步骤: , 2是第一个素数。也是第一个新素数。取出 2。 。 (最小的)是新素数。取出这个新素数。 1和2直到没有数存在。 Eratosthenes 筛法 6 O(n) 筛素数 void Init() { int i,j,q,t=0; memset(mark,0,sizeof(mark)); n=1000; for(i=2;i<=n;i++) { if(mark[i]==0) { t++]=i; } for(j=0;t;j++) { if(prime[j] * i>n)break; mark[prime[j] * i]=prime[j]; if(mark[i]==prime[j]) { // printf("%d %d mark=%d\n",i,j,mark[i]); break; } } } } 内网 B、C题 7初等数论概念除法定理,余数除法定理:对任意整数 a和任意正整数 n, 存在唯一的整数 q和r,使得 a=qn+r ,其中0≤ r<n 。值q成为除法的商,值 r=a(mod n) 称为除法的余数。 8初等数论的概念公约数与最大公约数d是a的约数并且也是 b的约数,则 d是a 和b的公约数。两个不同时为 0的整数 a和b的最大公约数表示为 gcd(a, b) 。 9初等数论的概念 gcd(a, b) 的性质: 定理:如果 a,b是不全为 0的任意整数,则 gcd(a, b)是a与b的线性组合{ax+by:x,y ∈ Z} 中的最小正元素。推论 1:对于任意整数 a,b,如果 d| a 并且 d| b , 则 d| gcd(a, b) 。推论 2:对于所有整数 a和b以及任意非负整数 n, gcd(an, bn)=n * gcd(a,b) 。推论 3:对所有正整数 n,a和b,如果 n| ab 并且 gcd(a, n)=1 ,则 n| b 。 10 初等数论的概念互质数: 如果两个整数 a与b只有公因数 1,即如果 gcd(a, b)=1 ,则 a与b称为互质数(互素) 。定理:对任意整数 a,b和p,如果 gcd(a, p)=1 且 gcd(b, p)=1 ,则 gcd(ab, p) = 1 。