高精度算法 从入门到进阶详解

高精度算法

算法须知

我们为什么要用高精度？

一些毒瘤题，数据范围超过了最大的整型，一个数字无法用一个变量储存。

那么我们如何储存？

用一个数组，每一个下标代表每一个数位上的一个数。

例如：$998244353$用数组储存下来，$A(3,5,3,4,4,2,8,9,9)$，一般是倒着存（从低位到高位，这样计算方便）。

简单入门

高精度储存数字

用字符串读入一个数，将其从右至左加入高精度数组。

	scanf("%s",&s+1);
	alen=strlen(s+1);
	for(i=1;i<=alen;i++) a[i]=s[alen-i+1]-'0';

$alen$为该数的位数，从$a[1]$至$a[alen]$分别表示该数的个位至最高位。

高精度比大小

对于比较两个数的大小，我们采用的方法如下：
1.比较两个数的位数，如果不一样，位数较大的数大；
2.如果两个数位数一样，则从高位向低位比较，当发现有一位的数字不同时，较大的数大；
3.如果到最后没有不一样的数字，那么两数相等。

如果$a$大于$b$返回真，否则返回假。

	if(alen>blen) return true;
	if(alen<blen) reutrn false;
	for(i=alen;i>0;i--)
	{
		if(a[i]>b[i]) return true;
		if(a[i]<b[i]) return false;
	}
	return fasle;

基础操作

竖式计算大家都会，用代码模拟竖式就行了。

高精度加法

和的每一位等于两个加数的对应位数的和，如果大于$9$则向前一位进$1$。

	slen=max(alen,blen);
	for(i=1;i<=slen;i++)
	{
		s[i]+=a[i]+b[i];
		s[i+1]=s[i]/10;
		s[i]%=10;
	}
	if(s[slen+1]>0) slen++;

高精度减法

差的每一位等于被减数的对应位数减去减数的对应位数，如果不够件则向前一位退$1$。
先判断答案的正负性，用较大的数减较小的数，可得到差的绝对值。

	slen=max(alen,blen);
	for(i=1;i<=slen;i++)
	{
		s[i]+=a[i]-b[i];
		if(s[i]<0) s[i]+=10,s[i+1]=-1;
	}
	while(s[slen]==0) slen--;

高精度乘法

用第一个因数的每一位与第二个因数的每一位分别相乘，第$i$位与第$j$位的积加在积的第$i+j-1$位。

	slen=alen+blen-1;
	for(i=1;i<=alen;i++)
	{
		for(j=1;j<=blen;j++)
		{
			s[i+j-1]+=a[i]*b[j];
			s[i+j]+=s[i+j-1]/10;
			s[i+j-1]%=10;
		}
	}
	if(s[slen+1]>0) slen++;

高精度整除单精度

从高位往低位除，把余数记录下，再乘$10$与后一位的数相加接着往下除。最后的商为$s$，余数为$x$。

	slen=alen;x=0;
	for(i=slen;i>0;i--)
	{
		s[i]=a[i]+x*10;
		x=s[i]%b;
		s[i]/=b;
	}
	while(s[slen]==0) slen--;

进阶优化

我们不难发现，高精度乘法的时间复杂度是两个因数位数的积，当它们过大时，时间会很大。同时，其它的高精度算法计算次数达到一定时，时间也会很大。
那么我们能否优化呢？

高精度压位

一般我们用数组的一个下标存储一个一位数，然而我们完全可以存储多位数，连续多位一起计算。
以下不妨设我们一个下标储存一个四位数。

读入

	scanf("%s",&s+1);
	len=strlen(s+1);
	for(i=len;i>0;i--) 
	{
		if((len-i)%4==0) a[++alen]=s[i]-'0';
		else a[len]=(s[i]-'0')*10+a[len];
	}

计算

其实很简单，只用把对$10$取余改成对$10000$取余即可。

输出

这里的难点在于不足$4$位的要补上$0$.

	for(i=alen;i>0;i--)
	{
		if(i<alen)
		{
			t=a[i],l=0;
			while(t>0)
			{
				t/=10;
				l++;
			}
			for(j=1;j<=4-l;j++) printf("0");
		}
		printf("%d",a[i]);
	}

拓展提升

以下两个算法都用到了二分的思想。此时的$l$，$r$，$mid$，$ans$都要用高精度储存。
只贴上单精度的代码，但所有运算均要使用高精度，上文均已给出。

高精度整除高精度

二分商，与除数相乘，和被除数比大小。令$a$除以$b$的商为$s$，余数为$x$。

	l=0;
	r=a;
	while(l<=r)
	{
		mid=(l+r)/2;
		if(mid*b<=a)
		{
			s=mid;
			l=mid+1;
		}
		else r=mid-1;
	}
	x=a-b*s;

高精度开方

与上面类似。令$s$为最大的平方小于等于$a$的整数。

	l=0;
	r=a;
	while(l<=r)
	{
		mid=(l+r)/2;
		if(mid*mid<=a)
		{
			s=mid;
			l=mid+1;
		}
		else r=mid-1;
	}

更多的题目实现需要用已有的知识灵活变通。
以上为高精度算法大部分内容。希望你能有所收获。