高精度运算

今天来讲讲高精度算法，一个我最不擅长的算法(_{字符串的处理太恶心了})。

高精度虽然是个省选都不会考的东西，但是对于有些很恶心的题还是有必要用一下。

1. 高精度的存储

用数组存即可。

选择用 $a[0]$ 存储数的位数，$a[1]\sim a[a[0]]$ 存储数的个位，十位直到最高位。

#define maxn 2e5
int a[maxn];

2. 高精度的输入输出

用字符串形式输入，然后转换存入 $a$ 数组。

输出则倒序输出 $a$ 数组。

char s[maxn];
void bigscanf(int *a) //输入
{
   	scanf("%s",s);
   	a[0]=strlen(s); //长度
   	for(int i=0,j=a[0];i<a[0];i++,j--) //倒着存储
     	a[j]=s[i]-'0';
    while(a[0]>1&&a[a[0]]==0) //删掉前导0，防止一些恶心的数据
    	a[0]--;
}
void bigprintf(int *a) //输出
{
    for(int i=a[0];i>0;i--) //倒序
      	printf("%d",a[i]);
    printf("\n");
}

3. 低精度整数转为高精度

就是把各位数字分解开存进去即可。

void int2big(int x,int *a) //x转换进a数组
{
    if(x==0)
    {
        a[0]=1;
        a[1]=0;
    } //特判
    int k=0;
    while(x>0)
    {
        k++;
        a[k]=x%10;
        x=x/10;
    } //转换
    a[0]=k;
}

4. 高精度整数的比较

比较 $a$ 数组和 $b$ 数组存的数的大小。

如果 $a>b$ 返回 $1$，如果 $a=b$ 返回 $0$，如果 $a<b$ 返回 $-1$。

int bigcmp(int *a,int *b)
{
   	if(a[0]>b[0])
        return 1;
   	if(a[0]<b[0]) //先比较长度
        return -1;
  	for(int i=a[0];i>0;i--)
  	{
     	if(a[i]>b[i]) //再从高位到低位依次对比
            return 1;
     	if(a[i]<b[i])
            return -1;
   	}
   	return 0;
}

5. 高精度加法

模拟一下进位即可，$a+b=c$。

void bigadd(int* a,int* b,int* c)
{
    int k=a[0]>b[0]?a[0]:b[0];//取最大长度
    int g=0; //进位
    for(int i=1;i<=k;i++)
    {
       	c[i]=a[i]+b[i]+g;
        g=c[i]/10;
        c[i]=c[i]%10;
    }
    if(g>0)
    {
       	k++;
       	c[k]=g;
    }
    c[0]=k;
}

6. 高精度减法

计算 $c=a-b$，但是在调用前先判断是否 $a\ge b$。

void bigsub(int* a,int* b,int* c)
{
    int k=a[0],g=0;
    for(int i=1;i<=k;i++)
    {
        c[i]=a[i]-b[i]-g;
        if(c[i]<0)
        {
           	g=1;
           	c[i]=c[i]+10;
        }
        else
            g=0;
    }
    while(k>1&&c[k]==0) //前导0
    	k--;
    c[0]=k;
}

7. 高精度乘法

(1) 高精度乘低精度

void bigmul1(int *a,int b,int *c)
{
    int k=a[0],g=0;
    for(int i=1;i<=a[0];i++)
    {
         c[i]=a[i]*b+g;
         g=c[i]/10;
         c[i]=c[i]%10;
    }
 	while(g>0) //分解 g 的各位数字
    {
       k++;
       c[k]=g%10;
       g=g/10;
    }
    while(k>1&&c[k]==0)
        k--;
    c[0]=k;
}

(2) 高精度乘高精度

首先：一个 $a[0]$ 位的整数与一个 $b[0]$ 位的整数的乘积位数不会超过 $a[0]+b[0]$ 位；
然后：$a$ 的第 $i$ 位和 $b$ 的第 $j$ 位相乘，这个乘积在乘积 $c$ 的第 $i+j-1$ 位；
最后：模拟乘法的手算过程，并将 $a[i]\times b[j]$ 的 结 果 累 加 在 $c[i+j-1]$ 中，并考虑向 $c[i+j]$ 进位的情况。

void bigmul2(int* a,int* b,int* c)
{
    int k=a[0]+b[0];
    for(int i=1;i<=a[0];i++)
      	for(int j=1;j<=b[0];j++)
      	{
          	c[i+j-1]=c[i+j-1]+a[i]*b[j];
          	c[i+j]=c[i+j]+c[i+j-1]/10;
          	c[i+j-1]=c[i+j-1]%10;
      	}
    while(k>1&&c[k]==0)
    	k--;
    c[0]=k;
}

8. 高精度除法

(1) 高精度除以低精度

$a$ 是被除数；$b$ 是除数；$c$ 是商，高精度；$d$ 是余数，低精度。

void bigdiv1(int *a,int b,int *c,int &d)
{
   	int k=a[0];
   	d=0;
   	for(int i=k;i>=1;i--)
   	{
      	d=d*10+a[i];
      	c[i]=d/b;
      	d=d%b;
   	}
   	while(k>1&&c[k]==0)
   		k--;
   	c[0]=k;
}

(2) 高精度除以高精度

同理。

void bigdiv2(int* a,int* b,int* c,int* d)
{
    int k=a[0];
    d[0]=1;
    d[1]=0;
    for(int i=k;i>0;i--)
    {
        bigmul1(d,10,d); //d=10d+a[i]
        d[1]=a[i];
        while(bigcmp(d,b)>=0)  //减的次数是商
        {
        	bigsub(d,b,d);
            c[i]=c[i]+1;
        }
    }
    while(c[k]==0&&k>1)
    	k--;
    c[0]=k;
}

9. 高精度排序

用 bigcmp 函数轻松搞定。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<ctime>
#define INF 1e9
using namespace std;
const int maxn=1010;
int n;
char s[maxn];
int a[maxn][maxn];
void bigscanf(int k)
{
   scanf("%s",s);
   a[k][0]=strlen(s);
   for(int i=0,j=a[k][0];i<a[k][0];i++,j--)
     	a[k][j]=s[i]-'0';
}
int bigcmp(int x,int y)
{
   if(a[x][0]>a[y][0])
   		return 1;
   if(a[x][0]<a[y][0])
   		return -1;
   for(int i=a[x][0];i>0;i--)
   {
     	if(a[x][i]>a[y][i])
     		return 1;
     	if(a[x][i]<a[y][i])
     		return -1;
   }
   return 0;
}
void bigprintf(int k)
{
    for(int i=a[k][0];i>0;i--)
      	printf("%d",a[k][i]);
    printf("\n");
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		bigscanf(i);
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
			if(bigcmp(i,j)==1)
				swap(a[i],a[j]);
	for(int i=1;i<=n;i++)
		bigprintf(i);
	return 0;
}