huangx607087 学习数论的笔记2
1.素数及其计数(数论概论章)
定理1.是唯一的偶素数
定理2.素数有无穷多个,若为任意整数,满足,那么有无穷多个素数满足.
定理3.区间内必有一个素数
定理4.设为不超过的素数个数,那么接近于,也就是
哥德巴赫猜想:每一个大于等于的偶数都可以表示为个素数之和。
孪生素数:均为素数,那么构成一对孪生素数,猜想有无限多个这样的素数组。
素数猜想3:可能存在无穷多个类型的素数
2.梅森素数(形如的素数)(数论概论章)
若是素数,那么
性质1:若被整除,那么被整除。所以我们有推论:若是个素数,则一定是个素数。
性质2:如果是素数,那么是个完全数(完全数是指除了它的本身之外,这个数的所有因子之和等于它本身,比如)
性质3:所有大于的完全数在进制中均以结尾
设为的所有因子之和(包括两个数),例如:
性质4:若,则。
性质5:若为素数,则。也就是对于任何素数,均有。
以下为求结果的后8位十进制数的代码,也就是对一亿取模的值,其中用到了二分快速加,可以推导一下(等比数列里千万不不要用除法!!!!)
1 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 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
| #include <bits/stdc++.h> using namespace std; int n,m,T,mod=100000000; int p[4000],c[4000],num; void dividing(int x) { int i; for(i=2;i*i<=x;i++) { if(x%i==0) { p[++num]=i; c[num]=0; while(!(x%i)) x/=i,++c[num]; } } if(x>1) p[++num]=x,c[num]=1; } long long pw(int x,int y) { if(y==0) return 1; if(y==1) return x; if(x==0) return 0; long long S=pw(x,y/2)%mod; if(y%2) return S*S*x%mod; else return S*S%mod; } long long ad(int q,int k) { if(k==0) return 1; if(k==1) return q+1; long long S=ad(q,(k-1)/2); if(k%2) return S+pw(q,(k+1)/2)*S%mod; else return S+pw(q,k/2)*S+pw(q,k)%mod; } int main() { int i,j; scanf("%d",&T); while(T--) { int a,b; scanf("%d%d",&a,&b); dividing(a); long long S=1; for(i=1;i<=num;i++) { S*=ad(p[i],c[i]); S%=mod; } printf("%lld\n",S); } return 0; }
C++
|
3.二分快速幂 (数论概论第章)
二分快速幂的C++代码 (Python中直接用pow(x,y,z)
函数,很方便)。
1 2 3 4 5 6 7 8 9
| long long pw(int x,int y) { if(y==0) return 1; if(y==1) return x; if(x==0) return 0; long long S=pw(x,y/2)%mod; if(y%2) return S*S*x%mod; else return S*S%mod; }
C++
|
4.解方程 (数论概论第章)
前提条件:且。
步骤:
1.计算
2.求的逆元
3.计算
举个例子:求
1.计算
2.在模的意义下乘法逆元为
3.
这是什么?? RSA解密 RSA解密 RSA解密!! 密码学的知识成功地跟数论联系起来了(奇怪的知识增加了)23333333