提高班第四讲初等数论

《提高班第四讲初等数论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、初等数论题Presentedby汪演增------------------Achilles@USC目录1、素数2、快速幂取模3、唯一质因子分解定理3、最大公约数（欧几里得算法）4、扩展欧几里得算法5、同余以及线性同余方程6、特殊的线性同余方程组：中国剩余定理素数1、判断n是否为素数for(inti=2;i*i<=n;i++)if(n%i==0){flag=1;break;}2、如果要求10^6区间内的素数呢？概念：除了1和此整数自身外，不能被其他自然数整除的数。2）给定一个范围（求这个范围内的素数

2、），进行如下步骤：0.从2开始，2是第一个素数。也是第一个新素数。取出2。1.筛掉所有新素数的倍数。2.留下来的数里面第一个（最小的）是新素数。取出这个新素数。3.重复1和2直到没有数存在。Eratosthenes筛法memset(flag,0,sizeof(flag));for(inti=2;i*i<=1000000;i++)if(!flag[i]){for(intg=i;g<=1000000;g+=i)flag[g]=1;}快速幂取模1、10^8怎么求？3、10^（10^8）%9999

3、?2、10^180呢？1.模取运算的性质(1)(a+b)%c=((a%c)+(b%c))%c(2)(a*b)%c=((a%c)*b)%c10.__int64fn(__int64a,__int64k)11.{12.if(k==0)return1;13.if(k==1)returna%mod;14.__int64tmp1=fn(a,k/2);15.__int64tmp2=tmp1*tmp1%mod;16.if(k&1)returntmp2*a%mod;17.returntmp2;18.

4、}(a^k)%mod快速幂（风格简洁）__int64quickmod(__int64x,__int64n){__int64pw=1;while(n>0){if(n&1)//n&1等价于(n%2)==1pw*=x;x*=x;n>>=1;//n>>=1等价于n/=2}returnpw;}质因子分解定理唯一因子分解唯一质因子分解定理：合数a仅能以一种方式，写成如下的乘积形式：a=p1e1p2e2…prer其中pi为素数，p1

5、1、先求出每一个n的素因子，然后穷举筛选法的妙用：思路不明白没关系，看代码for(inti=2;i*i<=n;){if(n%i==0){cout<

6、的约数，则d是a和b的公约数。两个不同时为0的整数a和b的最大公约数表示为gcd(a,b)。互质数：如果两个整数a与b只有公因数1，即如果gcd(a,b)=1，则a与b称为互质数（互素）。定理：对任意整数a，b和p，如果gcd(a,p)=1且gcd(b,p)=1，则gcd(ab,p)=1。最大公约数gcd（最大公因子）Euclidean算法求两个正整数a和b的gcd。先令r0为a，r1为b，接着执行如下运算：GCD递归定理：对任意非负整数a和任意正整数b，gcd(a,b)=gcd(b,amodb)

7、。例：求8251和6105的最大公因数。8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4最后除数37是148和37的最大公因数，也就是8251与6105的最大公因数。欧几里德算法（辗转相除法）：intgcd(a,b){//returnb?gcd(b,a%b):a;if(!b)returna;returngcd(b,a%b);}LCM(LeastCommonMultiple)有了GCD,

8、LCM就好办了LCM(a,b)=a*b/GCD(a,b)实际上最好写成a/GCD(a,b)*b思考：为什么下面的写法好？扩展欧几里得算法扩展欧几里得定理：对于不完全为0的非负整数a，b，gcd（a，b）表示a，b的最大公约数d，必然存在整数对x，y，使得gcd（a，b）=d=ax+by。扩展欧几里德算法是用来在已知a,b求解一组x，y使得ax+by=Gcd(a,b)=d设a>b。1、显然当b=0时，gcd（a，b）=a。此时x=1，y=0；2、ab！=0时，设ax1+by1=gcd