初等数论程耀

1、初等数论程耀第1页，共23页，2022年，5月20日，13点34分，星期一素数和合数算术基本定理：任意正整数n可以写成n=2a1*3a2*5a3*,其中a1,a2,a3等为非负整数素数的判定： 判定函数 筛法求素数 miller_rabin素性判定第2页，共23页，2022年，5月20日，13点34分，星期一素数的判定bool Is_prime( int n)int t = (int )sqrt (n);for ( int i =2; i = t ; i +）if(n%i =0)return false;return true;第3页，共23页，2022年，5月20日，13点34分，星期一筛法

2、求素数思考：如果一个数是合数，那么它的素因子都比它小？这样说来：如果我们的当前数是 a ,那么所有 a的倍数（当然是2倍以上啦）都不会是素数，可以这样看吧？于是，我们可以一种新的素数判定方法。第4页，共23页，2022年，5月20日，13点34分，星期一筛法求素数方法：每次用一个素数，去筛掉所有它的倍数。举个例子：2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 2829 30筛去2的倍数，剩下3 5 7 9 11 13 15 17 19 21 23 25 27 29筛去3的倍数，剩下5 7 11 13

3、17 19 25 29 。注意：开头的数一定是素数？第5页，共23页，2022年，5月20日，13点34分，星期一筛法求素数bool prime maxn ;/时间复杂度O(n)?void init ( )memset(prime, 0 ,sizeof(prime);for( int i=4;i maxn; i +=2) primei=1;for( int i=3; i maxn; i+=2)if( ! prime i ) for ( int j = i * i ; j maxn;j+=i) prime j =1;第6页，共23页，2022年，5月20日，13点34分，星期一miller_ra

4、bin素性判定miller_rabin是一种概率型的算法，不是确定型的。但是，只要运行次数足够多，一般出错的概率是非常小的，一般10次就好了！算法复杂度是 O(logn)3)算法的正确性是基于费马小定理。费马小定理：对于素数p和任意整数a，有a(p-1)=1(mod p)。反过来，满足a(p-1)=1(mod p),p也几乎一定是素数。第7页，共23页，2022年，5月20日，13点34分，星期一miller_rabin算法分析bool miller_rabin(LL n) if(n2) return false; if(n=2) return true; if(!(n&1) return f

5、alse; for(int i=1;i=1;t+;/这个地方是通过一个推论来优化的，x2=1(mod n),当那个n是合数的时候，就会出现非平凡平方根！ LL x=quick_mod(a,m,n); for(int i=1;i=t;i+) y=muti(x,x,n); if(y=1 & x!=1 & x!=n-1) return true; x=y; if(y!=1) return true; else return false;第9页，共23页，2022年，5月20日，13点34分，星期一快速幂取模题目：求出mn ( mod p) 的值，其中 m=10000, n=1;/n右移两位，相当于除

6、2t = t * t %n;return ret ; PS：与快速幂取模类似的还有矩阵快乘，这里不展开第12页，共23页，2022年，5月20日，13点34分，星期一最大公约数（gcd)普通算法：求出c=min( a , b),如果找到c|a&c|b,那么c减一，然后循环继续，直到 找到 c满足条件为止。欧几里得算法：int gcd(int a , int b)return b?gcd(b,a%b):a; 第13页，共23页，2022年，5月20日，13点34分，星期一欧几里得算法的证明证明：令m是a , b 的公约数，而a可以表示为a = n*b + r,其中r=0 & rb那么r = a

7、- n*b,可以知道r 能够被 m 整除。同理：如果m是r 和 b 的公约数。那么，a=n*b +r,所以，m也能够整除a.由上面的两条可知：a,b和b,r具有相同的公约数，故欧几里得算法成立。第14页，共23页，2022年，5月20日，13点34分，星期一扩展欧几里得算法应用：常用来求解形如a*x+b*y=gcd(a,b)的二元一次不定方程代码如下：void extended_gcd( int a, int b, int &x ,int &y)if(b=0) x=1; y=0; return;extended_gcd(b,a%b,x,y);int temp=x;x=y;y=temp-a/b*

8、y; 第15页，共23页，2022年，5月20日，13点34分，星期一扩展欧几里得算法分析证明：令d = gcd( a , b);a*x + b*y=d . b*x1+(a%b)*y1=d.那么我们可以由x1,y1的值反推出x,y的值。把两式联立，消去d,并且用a-a/b*b来替换a%b;然后可以令x=y1,推出y=x1-a/b*y1;第16页，共23页，2022年，5月20日，13点34分，星期一扩展欧几里得算法的注意事项形如a*x + b*y = c的方程,如果gcd(a,b)能够整除c,那么此方程有解，否则无解。并且它的特解形式为x=c/gcd(a,b)*x0 , y=c/gcd(a,b

9、)*y0 (其中 x0,y0是用扩展欧几里得算法求出的解）通解的形式：x=x0 - b/d*ty= y0 + a/d*t其中：t是整数。第17页，共23页，2022年，5月20日，13点34分，星期一a关于模n的乘法逆元什么是乘法逆元？如果a*b=1(mod n),那么b就是a 关于模n的乘法逆元，此时，也可以称作a与b互为乘法逆元。第18页，共23页，2022年，5月20日，13点34分，星期一乘法逆元的应用题目：输出C(n,m)%p,其中p是一个素数。n10000.思考：如果使用边除边模的方法，也会有出现大数，导致精度溢出。 (a/b)%p != (a%p)/(b%p)%p;解决方案：除以

10、一个数并取模，就相当于是乘以它的逆元然后再取模。第19页，共23页，2022年，5月20日，13点34分，星期一如何求解乘法逆元上式等价a*x+b*n=1的解，所以可以应用扩展欧几里得算法来求出x的值。为了保证x是正整数，通常需要加上：x=(x%n+n)%n；int inv(int a , int n)int x,y;extended_gcd(a,n,x,y);x=(x%n+n)%n;return x;第20页，共23页，2022年，5月20日，13点34分，星期一扩展阅读AC神牛被称为数学帝，里面收录了好多数论方面的知识，其中最经典的就是各种大数取模.笨小孩的博客：这个博客收录了各种数论题的分类，有志于做数论专题的同学可以参考。第21页，共23页，2022年，5月20日，13点34分，星期一最后一页 最值得一看的就是qinz大牛的ACM装逼录， 我已经看了不知道多少遍了，但是，总是感觉百看不厌。强烈推荐大家看看！ 最后的话：可能每个ac