初等数论c++.doc

备注：纯手写代码，注释。数论1、素数（1）暴力求解法根据素数的概念，没有1和其本身没有其他正因数的数。所以只需枚举比这个数小的数，看能整除即可；C+代码：#include#include#includeusing namespace std;bool determine(int number)if(n=2)return false;if(!n%2)return false;for(int i=3;isum;if(determine(sum)coutYES!;else coutNO!;return 0;时间复杂度：o(sqrt(n)/2);空间复杂度：几乎没有；（2）一般线性筛法：因为任何一个合数都能分解成几个素数相乘的形式；所以可以做一个表，首先把2设为质数，然后将2的倍数设为合数，剩下的数就是新得到的质数，然后重复这个过程，直到筛到合适的范围即可；但是这个算法有缺陷：1、 同一个数可能被筛多次，这就产生了多余的步骤。2、 占用空间很大，如果使用bool数组的话，只能筛到1e9；3、 从1-n筛，不能从m-n开始筛；C+代码：#include#include#includeusing namespace std;bool s1000000000;int m,n;int main()cinmn;memset(s,true,n);s0=s1=0;/输出MN之间所有素数；for(int i=2;i=ceil(sqrt(n);+i)if(si)for(int j=i;j=n;+j)if(si*j)si*j=false;for(int i=m;i=n;+i)if(si)couti ; return 0;时间复杂度：o(n*loglogn);空间复杂度：很大！注意数据大的话可能会爆空间；（3）线性筛法求素数这个占空间就更大了，需要使用一个bool数组和int数组而亲身试验得到int数组最多开到1e8很无语，快确实是快了，但是测试数据一大，爆空间就更容易了；#include#include#includeusing namespace std;int m,n,sum;bool inp1000000000;int s100000000=0,0;int main()cinmn;for(int i=2;i=n;+i)if(!inpi)ssum+=i;for(int j=0;jsum&i*sj=n;+j)inpi*sj=true;if(!(i*sj)break;for(int i=m;i=n;+i)if(!inpi)couti ;return 0;2、唯一分解定理任何数都可以被唯一的分解成多个素数之积例如：456=2*2*2*3*19；C+代码：#include#include#include#include#includeusing namespace std;bool s1000000;int m,n,sum=0,num;int Prime1212121;int zhi1500;void Primes()for(int i=1;i=num;+i)si=true;s0=s1=0;for(int i=2;i=num;+i)if(si)Prime+sum=i;for(int j=i;jnum;int number=num;Primes();if(snum)coutnum=num;return 0;coutnum1)for(int i=1;num1&i=sum;+i)if(!(num%Primei)zhi+flag=Primei;num/=Primei;sort(zhi+1,zhi+flag+1);coutzhi1;for(int i=2;i=flag;+i)cout*zhii;return 0;首先做一个质数表，并把质数存到数组里，然后用数模每个素数，如果为0则记录素数，最后排个序输出；4、 欧拉函数欧拉函数（n）为不大于n的与n互素的数的个数；A与B互素，表示a与b的最大公约数为1，即（a，b）=1；欧拉函数的符号读作fhi，在搜狗的特殊符号里可以找到；，其中pi为x的质因数，其中(1)=1（唯一与1互质的数是1本身）设n为正整数，以 (n)表示不超过n且与n互素的正整数的个数，称为n的欧拉函数值：NN，n(n)称为欧拉函数。几个性质（来自百度百科）1、若n是质数p的k次幂，因为除了p的倍数外，其他数都跟n互质。2、欧拉函数是积性函数若m,n互质，3、特殊性质：当n为奇数时，, 证明与上述类似。4、若n为质数则5、设p是素数，a是一个正整数，那么C+实现：#include#include#include#include#includeusing namespace std;bool s1000000;int m,n,sum=0,num;int Prime1212121;int zhi1500;bool asd1500;int phi(int n) int i,rea=n; for(i=2;i*i1) rea=rea-rea/n; return rea;void Primes()for(int i=1;i=num;+i)si=true;s0=s1=0;for(int i=2;i=num;+i)if(si)Prime+sum=i;for(int j=i;jnum;int number=num;Primes();if(num=1|!num)coutfhi(number)=;coutnum;return 0;if(snum)coutfhi(number)=1)for(int i=1;num1&i=sum;+i)if(!(num%Primei)zhi+flag=Primei;num/=Primei;int fenzi=1,fenmu=1;sort(zhi+1,zhi+flag+1);for(int i=1;i=flag;+i)if(!asdzhii)asdzhii=true;fenzi*=zhii-1;fenmu*=zhii;coutfhi(number)=number/fenmu*fenzi;/coutfhi(number)=fhi(number);/*这是另一种求欧拉函数值的方法*/return 0;5、欧几里得算法辗转相除法，根据公式(a,b)=(b,r)其中r为a%b，即a/b；C+代码：（1）递归#include#includeusing namespace std;int GCD(int a,int b)if(a%b) return GCD(b,a%b);else return b;int main()int a,b;cinab;coutGCD(a,b);return 0;（2）递推#includeusing namespace std;int main()int a,b,r;cinab;r=m%n;while(r!=0)a=b;b=r;r=m%n;coutn;return 0;6、扩展欧几里得扩展欧几里得又称斐蜀定理，对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然存在整数对 x，y ，使得 gcd（a，b）=ax+by；求同余方程#includevoid exgcb(int a,int b,int &x,int &y)if(!b)x=1;y=0;return;int q=a/b;int r=a%b;exgcb(b,r,y,x);y-=q*x;int main()int x,y;int a,b;scanf(%d %d,&a,&b);exgcb(a,b,x,y);while(x0)x+=b;printf(%d,x);return 0;求乘法逆元#includevoid exgcb(int a,int b,int &x,int &y)if(!b)x=1;y=0;return;int q=a/b;int r=a%b;exgcb(b,r,y,x);y-=q*x;int Multiplicative inverse(int a,int b)int x,y;int gcb=GCD(a,b,x,y);if(1%gcb)return -1;x*=1%gcb;b=abs(b);int answer=x%b;while(answer=0)answ