printf("%d",a[a[99]-i-1]);
printf("\n\n");
return;
}
intcmp(inta1[MAX],inta2[MAX])
{intl1,l2;
inti;
l1=a1[99];
l2=a2[99];
if(l1>l2)
return1;
if(l1return-1;
for(i=(l1-1);i>=0;i--)
{
if(a1[i]>a2[i])
return1;
if(a1[i]return-1;
}
return0;
}
voidmov(inta[MAX],int*b)
{
intj;
for(j=0;jb[j]=a[j];
return;
}
//大数相乘(向左移)
voidmul(inta1[MAX],inta2[MAX],int*c)
{
inti,j,y,x,z,w,l1,l2;
l1=a1[MAX-1];
l2=a2[MAX-1];
if(a1[MAX-2]=='-'&&a2[MAX-2]=='-')
c[MAX-2]=0;
elseif(a1[MAX-2]=='-')
c[MAX-2]='-';
elseif(a2[MAX-2]=='-')
c[MAX-2]='-';
for(i=0;i{
for(j=0;j{
x=a1[i]*a2[j];
y=x/10;
z=x%10;
w=i+j;
c[w]=c[w]+z;
c[w+1]=c[w+1]+y+c[w]/10;
c[w]=c[w]%10;
}
}
w=l1+l2;
if(c[w-1]==0)w=w-1;
c[MAX-1]=w;
return;
}
//大数相加,注意进位
voidadd(inta1[MAX],inta2[MAX],int*c)
{
inti,l1,l2;
intlen,temp[MAX];
intk=0;
l1=a1[MAX-1];
l2=a2[MAX-1];
if((a1[MAX-2]=='-')&&(a2[MAX-2]=='-'))
{
c[MAX-2]='-';
}
elseif(a1[MAX-2]=='-')
{
mov(a1,temp);
temp[MAX-2]=0;
sub(a2,temp,c);
return;
}
elseif(a2[MAX-2]=='-')
{
mov(a2,temp);
temp[98]=0;
sub(a1,temp,c);
return;
}
if(l1elselen=l2;
for(i=0;i{
c[i]=(a1[i]+a2[i]+k)%10;
k=(a1[i]+a2[i]+k)/10;
}
if(l1>len)
{
for(i=len;i{
c[i]=(a1[i]+k)%10;
k=(a1[i]+k)/10;
}
if(k!
=0)
{
c[l1]=k;
len=l1+1;
}
elselen=l1;
}
else
{
for(i=len;i{
c[i]=(a2[i]+k)%10;
k=(a2[i]+k)/10;
}
if(k!
=0)
{
c[l2]=k;
len=l2+1;
}
elselen=l2;
}
c[99]=len;
return;
}
//大数相减,注意借位
voidsub(inta1[MAX],inta2[MAX],int*c)
{
inti,l1,l2;
intlen,t1[MAX],t2[MAX];
intk=0;
l1=a1[MAX-1];
l2=a2[MAX-1];
if((a1[MAX-2]=='-')&&(a2[MAX-2]=='-'))
{
mov(a1,t1);
mov(a2,t2);
t1[MAX-2]=0;
t2[MAX-2]=0;
sub(t2,t1,c);
return;
}
elseif(a2[MAX-2]=='-')
{
mov(a2,t2);
t2[MAX-2]=0;
add(a1,t2,c);
return;
}
elseif(a1[MAX-2]=='-')
{
mov(a2,t2);
t2[MAX-2]='-';
add(a1,t2,c);
return;
}
if(cmp(a1,a2)==1)
{
len=l2;
for(i=0;i{
if((a1[i]-k-a2[i])<0)
{
c[i]=(a1[i]-a2[i]-k+10)%10;
k=1;
}
else
{
c[i]=(a1[i]-a2[i]-k)%10;
k=0;
}
}
for(i=len;i{
if((a1[i]-k)<0)
{
c[i]=(a1[i]-k+10)%10;
k=1;
}
else
{
c[i]=(a1[i]-k)%10;
k=0;
}
}
if(c[l1-1]==0)//使得数组C中的前面所以0字符不显示了,如1000-20=0980--->显示为980了
{
len=l1-1;
i=2;
while(c[l1-i]==0)//111456-111450=00006,消除0后变成了6
{
len=l1-i;
i++;
}
}
else
{
len=l1;
}
}
else
if(cmp(a1,a2)==(-1))
{
c[MAX-2]='-';
len=l1;
for(i=0;i{
if((a2[i]-k-a1[i])<0)
{
c[i]=(a2[i]-a1[i]-k+10)%10;
k=1;
}
else
{
c[i]=(a2[i]-a1[i]-k)%10;
k=0;
}
}
for(i=len;i{
if((a2[i]-k)<0)
{
c[i]=(a2[i]-k+10)%10;
k=1;
}
else
{
c[i]=(a2[i]-k)%10;
k=0;
}
}
if(c[l2-1]==0)
{
len=l2-1;
i=2;
while(c[l1-i]==0)
{
len=l1-i;
i++;
}
}
elselen=l2;
}
elseif(cmp(a1,a2)==0)
{
len=1;
c[len-1]=0;
}
c[MAX-1]=len;
return;
}
//取模数
voidmod(inta[MAX],intb[MAX],int*c)//c=amodb,注意:
经检验知道此处A和C的数组都改变了
{intd[MAX];
mov(a,d);
while(cmp(d,b)!
=(-1))//c=a-b-b-b-b-b.......until(c
{
sub(d,b,c);
mov(c,d);//c复制给a
}
return;
}
//大数相除(向右移)
//试商法,调用以后w为amodb,C为adivb
voiddivt(intt[MAX],intb[MAX],int*c,int*w)
{
inta1,b1,i,j,m;//w用于暂时保存数据
intd[MAX],e[MAX],f[MAX],g[MAX],a[MAX];
mov(t,a);
for(i=0;ie[i]=0;
for(i=0;id[i]=0;
for(i=0;ia1=a[MAX-1];
b1=b[MAX-1];
if(cmp(a,b)==(-1))
{
c[0]=0;
c[MAX-1]=1;
mov(t,w);
return;
}
elseif(cmp(a,b)==0)
{
c[0]=1;
c[MAX-1]=1;
w[0]=0;
w[MAX-1]=1;
return;
}
m=(a1-b1);
for(i=m;i>=0;i--)//例如341245/3=341245-300000*1--->41245-30000*1--->11245-3000*3--->2245-300*7--->145-30*4=25--->25-3*8=1
{
for(j=0;jd[j]=0;
d[i]=1;
d[MAX-1]=i+1;
mov(b,g);
mul(g,d,e);
while(cmp(a,e)!
=(-1))
{
c[i]++;
sub(a,e,f);
mov(f,a);//f复制给g
}
for(j=i;je[j]=0;
}
mov(a,w);
if(c[m]==0)c[MAX-1]=m;
elsec[MAX-1]=m+1;
return;
}
//解决了m=a*bmodn
voidmulmod(inta[MAX],intb[MAX],intn[MAX],int*m)
{
intc[MAX],d[MAX];
inti;
for(i=0;id[i]=c[i]=0;
mul(a,b,c);
divt(c,n,d,m);
for(i=0;iprintf("%d",m[m[MAX-1]-i-1]);
printf("\nmlengthis:
%d\n",m[MAX-1]);
}
//解决了m=a^pmodn的函数问题。
voidexpmod(inta[MAX],intp[MAX],intn[MAX],int*m)
{
intt[MAX],l[MAX],temp[MAX];//t放入2,l放入1
intw[MAX],s[MAX],c[MAX],b[MAX],i;
for(i=0;ib[i]=l[i]=t[i]=w[i]=0;
t[0]=2;t[MAX-1]=1;
l[0]=1;l[MAX-1]=1;
mov(l,temp);
mov(a,m);
mov(p,b);
while(cmp(b,l)!
=0)
{
for(i=0;iw[i]=c[i]=0;
divt(b,t,w,c);//c=pmod2w=p/2
mov(w,b);//p=p/2
if(cmp(c,l)==0)//余数c==1
{
for(i=0;iw[i]=0;
mul(temp,m,w);
mov(w,temp);
for(i=0;iw[i]=c[i]=0;
divt(temp,n,w,c);//c为余c=temp%n,w为商w=temp/n
mov(c,temp);
}
for(i=0;is[i]=0;
mul(m,m,s);//s=a*a
for(i=0;ic[i]=0;
divt(s,n,w,c);//w=s/n;c=smodn
mov(c,m);
}
for(i=0;is[i]=0;
mul(m,temp,s);
for(i=0;ic[i]=0;
divt(s,n,w,c);
mov(c,m);//余数s给m
m[MAX-2]=a[MAX-2];//为后面的汉字显示需要,用第99位做为标记
return;
//k=temp*k%n
}
intis_prime_san(intp[MAX])
{
inti,a[MAX],t[MAX],s[MAX],o[MAX];
for(i=0;is[i]=o[i]=a[i]=t[i]=0;
t[0]=1;
t[MAX-1]=1;
a[0]=2;//{2,3,5,7}
a[MAX-1]=1;
sub(p,t,s);
expmod(a,s,p,o);
if(cmp(o,t)!
=0)
{
return0;
}
a[0]=3;
for(i=0;iexpmod(a,s,p,o);
if(cmp(o,t)!
=0)
{
return0;
}
a[0]=5;
for(i=0;iexpmod(a,s,p,o);
if(cmp(o,t)!
=0)
{
return0;
}
a[0]=7;
for(i=0;iexpmod(a,s,p,o);
if(cmp(o,t)!
=0)
{
return0;
}
return1;
}