数论.docx
《数论.docx》由会员分享，可在线阅读，更多相关《数论.docx（16页珍藏版）》请在冰点文库上搜索。
数论
目录
1.ExGcd1
2.中国剩余定理1
2.1伪中国剩余定理：
2
2.2中国剩余定理不互质2
3素数判断3
3.1伪素数判定3
3.2求n的最小质数因子4
4.Pell方程6
5.素数筛选8
6.欧拉函数8
7模线性方程9
8模线性方程组9
1.ExGcd
解ax+by=n
Code:
llExGcd（lla,llb,ll&x,ll&y）{
if（b==0）{
x=1;y=0;
returna;
}
llgcd=ExGcd（b,a%b,x,y）;
lltmp=x,x=y,y=tmp-（a/b）*y;
returngcd;
}
2.中国剩余定理
llext_euclid（lla,llb,ll&x,ll&y）//求gcd（a,b）=ax+by
{
llt,d;
if（b==0）{x=1;y=0;returna;}
d=ext_euclid（b,a%b,x,y）;
t=x;
x=y;
y=t-a/b*y;
returnd;
}
llChina（llW[],llB[],llk,lltmp）//W为除数，B为剩余个数W>BK为组数
{
lli;
lld,x,y,a=0,m,n=1;
for（i=0;in*=W[i];
for（i=0;i{
m=n/W[i];
d=ext_euclid（W[i],m,x,y）;
a=（a+y*m*B[i]）%n;
}
a-=tmp;
if（a==0）returnn;
elseif（a<0）returna+=n;
elsereturna;
}
2.1伪中国剩余定理：
求在小于等于N的正整数中有多少个X满足：
Xmoda[0]=b[0],Xmoda[1]=b[1],Xmoda[2]=b[2],…,Xmoda[i]=b[i],…（0解题：
先出所有a[i]的最小公倍数k，这样在x+1到x+k（x为任意数字）的范围内最多就只存在一个数字满足条件，而1到n%k范围内有可能存在一个或者0个，所以~~~~~
不过因为有可能在x+1到x+k范围内不存在这样的数字满足条件，这时，所//有的数字都会无法满足条件。
这组数据是没有数字满足的的也就是0个。
这个不可以用中国剩余定理，W[]必须全部都是素数。
2.2中国剩余定理不互质
原理：
两个方程合并,此时b1,b2不必互质的。
x=c1（modb1）x=c2（modb2）
x=k1*b1+c1,x=k2*b2+c2
k1*b1=c2-c1（modb2）
令g=gcd（b1,b2）==>b1/g*k1-b2/g*k2=（c2-c1）/g,（c2-c1）/g是否为整数就能判断是否存在解，
根据扩展欧几里得可以求得k1,此时x=k1*b1+c1求得特解
通解：
x=k1*b1+c1（mod（b1*b2/g））。
llmm[10],rr[10];//n个数，mm除数，rr余数
llChina_remain（intn）
{
llm1,m2,r1,r2,d,c,t;
boolflag=0;
m1=mm[0],r1=rr[0];
for（lli=0;im2=mm[i+1];
r2=rr[i+1];
llx,y;
d=exgcd（m1,m2,x,y）;
c=r2-r1;
if（c%d）{flag=1;break;}
x=x*c/d;
t=m2/d;
x=（x%t+t）%t;
r1=m1*x+r1;
m1=m1*m2/d;
}
if（flag）return-1;
else{
if（r1==0&&n>1）{
r1=mm[0];for（inti=1;illans=1;for（inti=0;ir1=ans/r1;
}
if（r1==0&&n==1）r1=mm[0];
returnr1;
}
}
3素数判断
3.1伪素数判定
llmul（llA,llB,llC）{
returnA*B%C;
}
llmt（lln,lla）{
lls,t,mi=n-1;
llr;
for（s=mi,r=0;!
（s&1）;s>>=1,r++）;
for（t=a;s>>=1;）{
a=mul（a,a,n）;
if（s&1）t=mul（t,a,n）;
}
if（t==1||t==mi）return1;
while（--r）if（（t=mul（t,t,n））==mi）return1;
return0;
}
llpr（lln）{
if（n==1）return0;
if（n<29）returnn==2||n==3||n==5||n==7||n==11||n==13||n==17||n==19||n==23;
if（!
（n&1&&n%3&&n%5&&n%7&&n%11&&n%13&&n%17&&n%19&&n%23））return0;
return（n==17431||mt（n,34862）&&（n==3281359||mt（n,574237825）））;
}
intmain（）{
lln;
while（scanf（"%I64d",&n）!
=EOF）if（pr（n））puts（"YES"）;elseputs（"NO"）;
return0;
}
3.2求n的最小质数因子最大素因子
#defineC163811
usingnamespacestd;
#definellunsigned__int64
llMin;
llmulti（lla,llb,lln）{
lltmp=a%n,s=0;
while（b）{
if（b&1）s=（s+tmp）%n;
tmp=（tmp+tmp）%n;
b>>=1;
}
returns;
}
llPow（lla,llb,lln）{
lltmp=a%n,s=1;
while（b）{
if（b&1）s=multi（s,tmp,n）;
tmp=multi（tmp,tmp,n）;
b>>=1;
}
returns;
}
intwitness（lla,lln）{
llu=n-1,t=0,i,x,y;
while（!
（u&1））u>>=1,t++;
x=Pow（a,u,n）;
for（i=1;i<=t;i++）{
y=multi（x,x,n）;
if（y==1&&x!
=1&&x!
=n-1）return1;
x=y;
}
if（x!
=1）return1;
return0;
}
inttest（lln）{
lla;
inti;
if（n==2）return1;
if（n<2||!
（n&1））return0;
srand（（ll）time（0））;
for（i=0;ia=（（ll）rand（））%（n-2）+2;
if（witness（a,n））return0;
}
return1;
}
llgcd（lla,llb）{returnb?
gcd（b,a%b）:
a;}
llpollard_rho（lln,llc）{
llx,y,d,i=1,k=2;
srand（（ll）time（0））;
x=（（ll）rand（））%（n-1）+1;
y=x;
while
（1）{
i++;
x=（multi（x,x,n）+c）%n;
d=gcd（y-x+n,n）;
if（d!
=1&&d!
=n）returnd;
if（y==x）returnn;
if（i==k）y=x,k<<=1;
}
}
voidfind（lln,llc）{
llr;
if（n<=1）return;
if（test（n））{
if（Min>n）Min=n;
return;
}
r=pollard_rho（n,c--）;
find（n/r,c）;
find（r,c）;
}
llMaxPrimeFactor（lln）{
if（test（n））
returnn;
llk=-1,g;
Min=n;
find（n,C）;
g=MaxPrimeFactor（Min）;
k=g>k?
g:
k;
g=MaxPrimeFactor（n/Min）;
k=g>k?
g:
k;
returnk;
}
//if（test（n））{//测试素数
//printf（"Prime\n"）;
//continue;
//}
//Min=n;//Min是最小素因子（全局）
//find（n,C）;//获得
//printf（"%lld\n",Min）;
//printf（"%lld\n",MaxPrimeFactor（n））;//最大素因子
4．Pell方程
求x和y：
X^2-n*Y^2=1
求解第k个解：
（x1,y1）改成（x0,y0）
#definemaxn1000
#definell__int64
#definemod8191
structMarix{
llx[2][2];
};
Marixmul（Marixx,Marixy）{
Marixz;
lli,j,k;
memset（z.x,0,sizeof（z.x））;
for（i=0;i<2;i++）{
for（j=0;j<2;j++）{
for（k=0;k<2;k++）{
z.x[i][j]+=（x.x[i][k]%mod*（y.x[k][j]%mod））%mod;
z.x[i][j]%=mod;
}
}
}
returnz;
}
Marixpow（Marixx,lln）{
Marixsum;
sum.x[0][1]=sum.x[1][0]=0;
sum.x[0][0]=sum.x[1][1]=1;
while（n）{
if（n&1）sum=mul（sum,x）;
n=n>>1;
x=mul（x,x）;
}
returnsum;
}
voidGetMinPell（lln,ll&x,ll&y）{
llpp[33],qq[33],p[33],q[33],a[33];
lli,cnt,idx;
boolflag;
pp[0]=0,qq[0]=1,a[0]=sqrt（n）;
p[0]=a[0],q[0]=1;
pp[1]=a[0]*qq[0]-pp[0];
qq[1]=（n-pp[1]*pp[1]）/qq[0];
a[1]=（sqrt（n）+pp[1]）/qq[1];
p[1]=a[1]*p[0]+1,q[1]=a[1]*q[0];
flag=1;
cnt=100;
for（i=2;cnt--;i++）{
if（flag）cnt++;
pp[i]=a[i-1]*qq[i-1]-pp[i-1];
qq[i]=（n-pp[i]*pp[i]）/qq[i-1];
a[i]=（sqrt（n）+pp[i]）/qq[i];
if（flag&&a[i]==2*a[0]）{
if（!
（i&1））{
idx=i-1;
break;
}
else{
flag=0;
cnt=i;
idx=2*i-1;
}
}
p[i]=a[i]*p[i-1]+p[i-2],q[i]=a[i]*q[i-1]+q[i-2];
}
x=p[idx],y=q[idx];
}
intmain（）{
lln,x,y,k;
while（scanf（"%I64d%I64d",&n,&k）!
=EOF）{
if（n==1||n==4||n==9||n==16||n==25）{
printf（"Noanswerscanmeetsuchconditions\n"）;
continue;
}
GetMinPell（n,x,y）;
//printf（"%I64d%I64d\n",x,y）;
MarixMa;
Ma.x[0][0]=x,Ma.x[0][1]=y*n,Ma.x[1][0]=y,Ma.x[1][1]=x;
Ma=pow（Ma,k-1）;
printf（"%I64d\n",（Ma.x[0][0]*x+Ma.x[0][1]*y）%mod）;
}
}
5.素数筛选
for（i=2;i{
if（!
mark[i]）prime[size++]=i;
for（j=0;j{
mark[prime[j]*i]=1;
if（i%prime[j]==0）break;
}
}
6.欧拉函数
由欧拉函数为积性函数，即：
如果gcd（m,n）==1,则有φ（m*n）==φ（m）*φ（n）;且由φ（p^k）==（p-1）*p^（k-1），可得
φ（n）==φ（p1^k1*p2^k2*p3^k3*…*pt^kt）
==φ（p1^k1）*φ（p2^k2）*φ（p3^k3）*…*φ（pt^kt）
==（p1-1）*p1^（k1-1）*（p2-1）*p2^（k2-1）*（p3-1）*p3^（k3-1）*…*（pt-1）*pt^（kt-1）
==p1^k1*（1-1/p1）*p2^k2*（1-1/p2）*p3^k3*（1-1/p3）*…*pt^kt*（1-1/pt）
==n*（1-1/p1）*（1-1/p2）*（1-1/p3）*…*（1-1/pt）
于是有
f（n）==n/φ（n）==1/[（1-1/p1）*（1-1/p2）*（1-1/p3）*…*（1-1/pt）]
（1）
由
（1）式可知:
要使f（x）最大，须使x含尽量多的不同素数因子。
phi[1]=1;
for（i=1;i{
for（j=0;jif（i%prime[j]==0）{
phi[prime[j]*i]=prime[j]*phi[i];
break;
}
elsephi[prime[j]*i]=phi[i]*（prime[j]-1）;
}
}
7模线性方程
//对于求出的x满足有d个：
a*xmodn=b;
voidmodeq（inta,intb,intn）
{
intd,e,x,y;
d=extgcd（a,n,x,y）;
if（b%d!
=0）无解返回；
e=x*（b/d）%n;
for（inti=0;i（e+i*（n/d））%n都是x的解；
//这里要找最小解应为：
xmin=（e+n）%（n/d）;
//如果要找最大解应为：
xmax=xmin+（d-1）*（n/d）;
}
8模线性方程组
intModulo（int*a,int*r,intsize）
//X%a[]=r[]，求X.Sizeisthesizeofthearray.
{
inti;
for（i=1;i{
intc=r[i]-r[0];
intx,y;
intd=gcd（a[0],a[i],x,y）;
if（c%d）
return0;
c=c/d;
intt=a[i]/d;
x=（c*x%t+t）%t;
r[0]=x*a[0]+r[0];
a[0]=a[0]*a[i]/d;
r[0]=（r[0]%a[0]+a[0]）%a[0];
}
returnr[0];
}
升级会员 