200128网课内容总结

admin

一、整除
1、被2,3,5,9,11等数整除的数的特性 （例题 大整数加，乘的验算）
2、连续四个数的乘积+1是完全平方
3、a=bq+r (0<=r<|b|)
4、若a不是2或3的倍数，则a*a+23能被24整除
二、质数
1、试除法（质数表试除，6n+-1试除）
2、筛法 线性筛，6n+-1节约空间
3、素数个数 x/ln(x)
4、欧拉函数 （编程实现）
三、算术基本定理
1、唯一分解
2、约数个数
四、最大公约数
1、GCD EXTGCD
2、大整数GCD 除以2
五、同余
1、同余的+-*^运算
2、逆元的求法（extgcd，费马，递推）
3、中国剩余定理
4、a^x=b(%n)

经典代码：编程实现
试除法质数判断
筛法求质数
extGCD
多种做法做小凯的疑惑
LG1128
LG3811
UVA11754 UVA11426