大数（相加，高精度）模板

发布时间：2020-12-14 02:57:26 所属栏目：大数据来源：网络整理

导读：?????????????????????????????????????????????????????????? AC,bar 时间限制： 1000 ms ?|? 内存限制： 65535 KB 描述 ??zsjing一直很郁闷，为什么别人胡搞一下就可以AC。而他一胡搞就是Wrong呢?囧...... 经过多方调查，他终于发现了。原来只要在提交的代

?????????????????????????????????????????????????????????? AC,bar

时间限制： 1000 ms ?|? 内存限制： 65535 KB

描述

??zsjing一直很郁闷，为什么别人胡搞一下就可以AC。而他一胡搞就是Wrong呢?囧......

经过多方调查，他终于发现了。原来只要在提交的代码里加上一句"printf("ACn");"就可轻松解决这个世纪难题了。是不是很厉害？不信的话你可以试试。

?? 给出一些让你测试的数据。如果，答案是对的你就要输出“AC”（不包括引号），反之输出"NEXT_AC"。

少年测你RP的时候到了。

输入

输入多组数据。
每行给出一行字符：A [] B = C的固定格式。其中A，B均小于64位整数。[]表示四则运算。详细情况看样例。
输入的A，B，C均是正常的整数。数据保证合法！

输出

如果，答案是对的。输出"AC"，反之"NEXT_AC".

样例输入

样例输出

AC
AC
NEXT_AC
AC

由此题总结大数模板：

/************
大数模板：
*************/
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<string>
using  namespace std;
#define Max(a,b) a>b?a:b
#define Min(a,b) a>b?b:a
#define mem(a,b) memset(a,b,sizeof(a))
int dir[4][2]= {{0,1},{0,-1},{1,0},{-1,0}};
#define DIGIT   4      //四位隔开,即万进制
#define DEPTH   10000        //万进制
#define MAX     254
typedef int bignum_t[MAX+1];
/************************************************************************/
/* 读取操作数，对操作数进行处理存储在数组里                             */
/************************************************************************/
int read(bignum_t a,istream&is=cin)
{
    char buf[MAX*DIGIT+1],ch ;
    int i,j ;
    memset((void*)a,sizeof(bignum_t));
    if(!(is>>buf))return 0 ;
    for(a[0]=strlen(buf),i=a[0]/2-1; i>=0; i--)
        ch=buf[i],buf[i]=buf[a[0]-1-i],buf[a[0]-1-i]=ch ;
    for(a[0]=(a[0]+DIGIT-1)/DIGIT,j=strlen(buf); j<a[0]*DIGIT; buf[j++]='0');
    for(i=1; i<=a[0]; i++)
        for(a[i]=0,j=0; j<DIGIT; j++)
            a[i]=a[i]*10+buf[i*DIGIT-1-j]-'0' ;
    for(; !a[a[0]]&&a[0]>1; a[0]--);
    return 1 ;
}

void write(const bignum_t a,ostream&os=cout)
{
    int i,j ;
    for(os<<a[i=a[0]],i--; i; i--)
        for(j=DEPTH/10; j; j/=10)
            os<<a[i]/j%10 ;
}

int comp(const bignum_t a,const bignum_t b)
{
    int i ;
    if(a[0]!=b[0])
        return a[0]-b[0];
    for(i=a[0]; i; i--)
        if(a[i]!=b[i])
            return a[i]-b[i];
    return 0 ;
}

int comp(const bignum_t a,const int b)
{
    int c[12]=
    {
        1
    }
    ;
    for(c[1]=b; c[c[0]]>=DEPTH; c[c[0]+1]=c[c[0]]/DEPTH,c[c[0]]%=DEPTH,c[0]++);
    return comp(a,c);
}

int comp(const bignum_t a,const int c,const int d,const bignum_t b)
{
    int i,t=0,O=-DEPTH*2 ;
    if(b[0]-a[0]<d&&c)
        return 1 ;
    for(i=b[0]; i>d; i--)
    {
        t=t*DEPTH+a[i-d]*c-b[i];
        if(t>0)return 1 ;
        if(t<O)return 0 ;
    }
    for(i=d; i; i--)
    {
        t=t*DEPTH-b[i];
        if(t>0)return 1 ;
        if(t<O)return 0 ;
    }
    return t>0 ;
}
/************************************************************************/
/* 大数与大数相加                                                       */
/************************************************************************/
void add(bignum_t a,const bignum_t b)
{
    int i ;
    for(i=1; i<=b[0]; i++)
        if((a[i]+=b[i])>=DEPTH)
            a[i]-=DEPTH,a[i+1]++;
    if(b[0]>=a[0])
        a[0]=b[0];
    else
        for(; a[i]>=DEPTH&&i<a[0]; a[i]-=DEPTH,i++,a[i]++);
    a[0]+=(a[a[0]+1]>0);
}
/************************************************************************/
/* 大数与小数相加                                                       */
/************************************************************************/
void add(bignum_t a,const int b)
{
    int i=1 ;
    for(a[1]+=b; a[i]>=DEPTH&&i<a[0]; a[i+1]+=a[i]/DEPTH,a[i]%=DEPTH,i++);
    for(; a[a[0]]>=DEPTH; a[a[0]+1]=a[a[0]]/DEPTH,a[a[0]]%=DEPTH,a[0]++);
}
/************************************************************************/
/* 大数相减(被减数>=减数)                                               */
/************************************************************************/
void sub(bignum_t a,const bignum_t b)
{
    int i ;
    for(i=1; i<=b[0]; i++)
        if((a[i]-=b[i])<0)
            a[i+1]--,a[i]+=DEPTH ;
    for(; a[i]<0; a[i]+=DEPTH,a[i]--);
    for(; !a[a[0]]&&a[0]>1; a[0]--);
}
/************************************************************************/
/* 大数减去小数(被减数>=减数)                                           */
/************************************************************************/
void sub(bignum_t a,const int b)
{
    int i=1 ;
    for(a[1]-=b; a[i]<0; a[i+1]+=(a[i]-DEPTH+1)/DEPTH,a[i]-=(a[i]-DEPTH+1)/DEPTH*DEPTH,i++);
    for(; !a[a[0]]&&a[0]>1; a[0]--);
}

void sub(bignum_t a,const bignum_t b,const int d)
{
    int i,O=b[0]+d ;
    for(i=1+d; i<=O; i++)
        if((a[i]-=b[i-d]*c)<0)
            a[i+1]+=(a[i]-DEPTH+1)/DEPTH,a[i]-=(a[i]-DEPTH+1)/DEPTH*DEPTH ;
    for(; a[i]<0; a[i+1]+=(a[i]-DEPTH+1)/DEPTH,i++);
    for(; !a[a[0]]&&a[0]>1; a[0]--);
}
/************************************************************************/
/* 大数相乘，读入被乘数a，乘数b，结果保存在c[]                          */
/************************************************************************/
void mul(bignum_t c,const bignum_t a,j ;
    memset((void*)c,sizeof(bignum_t));
    for(c[0]=a[0]+b[0]-1,i=1; i<=a[0]; i++)
        for(j=1; j<=b[0]; j++)
            if((c[i+j-1]+=a[i]*b[j])>=DEPTH)
                c[i+j]+=c[i+j-1]/DEPTH,c[i+j-1]%=DEPTH ;
    for(c[0]+=(c[c[0]+1]>0); !c[c[0]]&&c[0]>1; c[0]--);
}
/************************************************************************/
/* 大数乘以小数，读入被乘数a，乘数b，结果保存在被乘数                   */
/************************************************************************/
void mul(bignum_t a,const int b)
{
    int i ;
    for(a[1]*=b,i=2; i<=a[0]; i++)
    {
        a[i]*=b ;
        if(a[i-1]>=DEPTH)
            a[i]+=a[i-1]/DEPTH,a[i-1]%=DEPTH ;
    }
    for(; a[a[0]]>=DEPTH; a[a[0]+1]=a[a[0]]/DEPTH,a[0]++);
    for(; !a[a[0]]&&a[0]>1; a[0]--);
}

void mul(bignum_t b,const int d)
{
    int i ;
    memset((void*)b,sizeof(bignum_t));
    for(b[0]=a[0]+d,i=d+1; i<=b[0]; i++)
        if((b[i]+=a[i-d]*c)>=DEPTH)
            b[i+1]+=b[i]/DEPTH,b[i]%=DEPTH ;
    for(; b[b[0]+1]; b[0]++,b[b[0]+1]=b[b[0]]/DEPTH,b[b[0]]%=DEPTH);
    for(; !b[b[0]]&&b[0]>1; b[0]--);
}
/**************************************************************************/
/* 大数相除,读入被除数a，除数b，结果保存在c[]数组                         */
/* 需要comp()函数                                                         */
/**************************************************************************/
void div(bignum_t c,bignum_t a,const bignum_t b)
{
    int h,l,m,i ;
    memset((void*)c,sizeof(bignum_t));
    c[0]=(b[0]<a[0]+1)?(a[0]-b[0]+2):1 ;
    for(i=c[0]; i; sub(a,c[i]=m,i-1),i--)
        for(h=DEPTH-1,l=0,m=(h+l+1)>>1; h>l; m=(h+l+1)>>1)
            if(comp(b,i-1,a))h=m-1 ;
            else l=m ;
    for(; !c[c[0]]&&c[0]>1; c[0]--);
    c[0]=c[0]>1?c[0]:1 ;
}

void div(bignum_t a,const int b,int&c)
{
    int i ;
    for(c=0,i=a[0]; i; c=c*DEPTH+a[i],a[i]=c/b,c%=b,i--);
    for(; !a[a[0]]&&a[0]>1; a[0]--);
}
/************************************************************************/
/* 返回大数的长度                                                       */
/************************************************************************/
int length(const bignum_t a)
{
    int t,ret ;
    for(ret=(a[0]-1)*DIGIT,t=a[a[0]]; t; t/=10,ret++);
    return ret>0?ret:1 ;
}
/************************************************************************/
/* 返回指定位置的数字，从低位开始数到第b位，返回b位上的数               */
/************************************************************************/
int digit(const bignum_t a,const int b)
{
    int i,ret ;
    for(ret=a[(b-1)/DIGIT+1],i=(b-1)%DIGIT; i; ret/=10,i--);
    return ret%10 ;
}
/************************************************************************/
/* 返回大数末尾0的个数                                                  */
/************************************************************************/
int zeronum(const bignum_t a)
{
    int ret,t ;
    for(ret=0; !a[ret+1]; ret++);
    for(t=a[ret+1],ret*=DIGIT; !(t%10); t/=10,ret++);
    return ret ;
}

void comp(int*a,const int l,const int h,j,t ;
    for(i=l; i<=h; i++)
        for(t=i,j=2; t>1; j++)
            while(!(t%j))
                a[j]+=d,t/=j ;
}

void convert(int*a,bignum_t b)
{
    int i,t=1 ;
    memset(b,sizeof(bignum_t));
    for(b[0]=b[1]=1,i=2; i<=h; i++)
        if(a[i])
            for(j=a[i]; j; t*=i,j--)
                if(t*i>DEPTH)
                    mul(b,t),t=1 ;
    mul(b,t);
}
#define SGN(x) ((x)>0?1:((x)<0?-1:0))
#define ABS(x) ((x)>0?(x):-(x))
int read(bignum_t a,int&sgn,istream&is=cin)
{
    char str[MAX*DIGIT+2],ch,*buf ;
    int i,sizeof(bignum_t));
    if(!(is>>str))return 0 ;
    buf=str,sgn=1 ;
    if(*buf=='-')sgn=-1,buf++;
    for(a[0]=strlen(buf),j=0; j<DIGIT; j++)
            a[i]=a[i]*10+buf[i*DIGIT-1-j]-'0' ;
    for(; !a[a[0]]&&a[0]>1; a[0]--);
    if(a[0]==1&&!a[1])sgn=0 ;
    return 1 ;
}
struct bignum
{
    bignum_t num ;
    int sgn ;
public :
    inline bignum()
    {
        memset(num,sizeof(bignum_t));
        num[0]=1 ;
        sgn=0 ;
    }
    inline int operator!()
    {
        return num[0]==1&&!num[1];
    }
    inline bignum&operator=(const bignum&a)
    {
        memcpy(num,a.num,sizeof(bignum_t));
        sgn=a.sgn ;
        return*this ;
    }
    inline bignum&operator=(const int a)
    {
        memset(num,sizeof(bignum_t));
        num[0]=1 ;
        sgn=SGN (a);
        add(num,sgn*a);
        return*this ;
    }
    ;
    inline bignum&operator+=(const bignum&a)
    {
        if(sgn==a.sgn)add(num,a.num);
        else if
        (sgn&&a.sgn)
        {
            int ret=comp(num,a.num);
            if(ret>0)sub(num,a.num);
            else if(ret<0)
            {
                bignum_t t ;
                memcpy(t,num,sizeof(bignum_t));
                memcpy(num,sizeof(bignum_t));
                sub (num,t);
                sgn=a.sgn ;
            }
            else memset(num,sizeof(bignum_t)),num[0]=1,sgn=0 ;
        }
        else if(!sgn)
            memcpy(num,sgn=a.sgn ;
        return*this ;
    }
    inline bignum&operator+=(const int a)
    {
        if(sgn*a>0)add(num,ABS(a));
        else if(sgn&&a)
        {
            int  ret=comp(num,ABS(a));
            if(ret>0)sub(num,ABS(a));
            else if(ret<0)
            {
                bignum_t t ;
                memcpy(t,sizeof(bignum_t));
                memset(num,sizeof(bignum_t));
                num[0]=1 ;
                add(num,ABS (a));
                sgn=-sgn ;
                sub(num,t);
            }
            else memset(num,sgn=0 ;
        }
        else if
        (!sgn)sgn=SGN(a),add(num,ABS(a));
        return*this ;
    }
    inline bignum operator+(const bignum&a)
    {
        bignum ret ;
        memcpy(ret.num,sizeof (bignum_t));
        ret.sgn=sgn ;
        ret+=a ;
        return ret ;
    }
    inline bignum operator+(const int a)
    {
        bignum ret ;
        memcpy(ret.num,sizeof (bignum_t));
        ret.sgn=sgn ;
        ret+=a ;
        return ret ;
    }
    inline bignum&operator-=(const bignum&a)
    {
        if(sgn*a.sgn<0)add(num,sizeof(bignum_t));
                sub(num,t);
                sgn=-sgn ;
            }
            else memset(num,sgn=0 ;
        }
        else if(!sgn)add (num,a.num),sgn=-a.sgn ;
        return*this ;
    }
    inline bignum&operator-=(const int a)
    {
        if(sgn*a<0)add(num,ABS(a));
                sub(num,sgn=0 ;
        }
        else if
        (!sgn)sgn=-SGN(a),ABS(a));
        return*this ;
    }
    inline bignum operator-(const bignum&a)
    {
        bignum ret ;
        memcpy(ret.num,sizeof(bignum_t));
        ret.sgn=sgn ;
        ret-=a ;
        return ret ;
    }
    inline bignum operator-(const int a)
    {
        bignum ret ;
        memcpy(ret.num,sizeof(bignum_t));
        ret.sgn=sgn ;
        ret-=a ;
        return ret ;
    }
    inline bignum&operator*=(const bignum&a)
    {
        bignum_t t ;
        mul(t,a.num);
        memcpy(num,t,sizeof(bignum_t));
        sgn*=a.sgn ;
        return*this ;
    }
    inline bignum&operator*=(const int a)
    {
        mul(num,ABS(a));
        sgn*=SGN(a);
        return*this ;
    }
    inline bignum operator*(const bignum&a)
    {
        bignum ret ;
        mul(ret.num,a.num);
        ret.sgn=sgn*a.sgn ;
        return ret ;
    }
    inline bignum operator*(const int a)
    {
        bignum ret ;
        memcpy(ret.num,sizeof (bignum_t));
        mul(ret.num,ABS(a));
        ret.sgn=sgn*SGN(a);
        return ret ;
    }
    inline bignum&operator/=(const bignum&a)
    {
        bignum_t t ;
        div(t,a.num);
        memcpy (num,sizeof(bignum_t));
        sgn=(num[0]==1&&!num[1])?0:sgn*a.sgn ;
        return*this ;
    }
    inline bignum&operator/=(const int a)
    {
        int t ;
        div(num,ABS(a),t);
        sgn=(num[0]==1&&!num [1])?0:sgn*SGN(a);
        return*this ;
    }
    inline bignum operator/(const bignum&a)
    {
        bignum ret ;
        bignum_t t ;
        memcpy(t,sizeof(bignum_t));
        div(ret.num,a.num);
        ret.sgn=(ret.num[0]==1&&!ret.num[1])?0:sgn*a.sgn ;
        return ret ;
    }
    inline bignum operator/(const int a)
    {
        bignum ret ;
        int t ;
        memcpy(ret.num,t);
        ret.sgn=(ret.num[0]==1&&!ret.num[1])?0:sgn*SGN(a);
        return ret ;
    }

    inline int operator==(const bignum&a)
    {
        return(sgn==a.sgn)?!comp(num,a.num):0 ;
    }
    inline int operator==(const int a)
    {
        return(sgn*a>=0)?!comp(num,ABS(a)):0 ;
    }
    inline int operator!=(const bignum&a)
    {
        return(sgn==a.sgn)?comp(num,a.num):1 ;
    }
    inline int operator!=(const int a)
    {
        return(sgn*a>=0)?comp(num,ABS(a)):1 ;
    }
    friend inline istream&operator>>(istream&is,bignum&a)
    {
        read(a.num,a.sgn,is);
        return  is ;
    }
    friend inline ostream&operator<<(ostream&os,const bignum&a)
    {
        if(a.sgn<0)
            os<<'-' ;
        write(a.num,os);
        return os ;
    }
    inline int length()
    {
        return :: length(num);
    }
};
int main()
{
    /*int n,i,a,c;//注意bignum是一个类，输入只能用cin
    char q1,q2;
    while(scanf("%d %c %d %c %d",&a,&q1,&b,&q2,&c)!=EOF)
    {
        if(q1=='+')
        {
            if((a+b)==c)
                printf("ACn");
            else printf("NEXT_ACn");
        }
        if(q1=='-')
        {
            if((a-b)==c)
                printf("ACn");
            else printf("NEXT_ACn");
        }
        if(q1=='*')
        {
            if((a*b)==c)
                printf("ACn");
            else printf("NEXT_ACn");
        }
          if(q1=='/')
          {
               if((a/b)==c)
                printf("ACn");
            else printf("NEXT_ACn");
          }
      }
    }*/
    bignum a,c;
    char q1,q2;
    while(cin>>a)
    {
        scanf(" %c ",&q1),cin>>b;
        scanf(" %c ",&q2),cin>>c;
        bignum MM;
        if(q1=='+')
            MM=a+b;
        else if(q1=='-')
            MM=a-b;
        else if(q1=='*')
            MM=a*b;
        else if(q1=='/')
            MM=a/b;
        else
            MM=c+1;
        if(MM==c)
            puts("AC");
        else
            puts("NEXT_AC");
    }
    return 0;
}

大数相加：

计算：样例输入

2
1 2
112233445566778899 998877665544332211

样例输出

Case 1:
1 + 2 = 3
Case 2:
112233445566778899 + 998877665544332211 = 2222222222222221110

java版：

import java.math.BigInteger;
import java.util.Scanner;
public class Main{

    public static void main(String args[]) {
       Scanner cin=new Scanner(System.in);
       int n=cin.nextInt();
       BigInteger a,b;
       for(int i=1;i<=n;i++){
    	   a=cin.nextBigInteger();
    	   b=cin.nextBigInteger();
    	   System.out.println("Case "+i+":");
    	   System.out.println(a.toString()+" + "+b.toString()+" = "+a.add(b));
       }
    }
}

字符串处理大数模板：

 
#include<stdio.h>
#include<string.h>
int main()
{
	int z,x=0,a[1001],b[1001],k,k1,k2;
	char c[1001],d[1001];
	scanf("%d",&z);
	while(z--)
	{
		memset(a,sizeof(a));
		memset(b,sizeof(b));
		scanf("%s%s",c,d);
		k1=strlen(c);
		k2=strlen(d);
		k=(k1>k2)?k1:k2;
		for(i=k;k1>0;i--,k1--)
			a[i]=c[k1-1]-48;
		for(i=k;k2>0;i--,k2--)
			b[i]=d[k2-1]-48;
		for(i=k;i>=1;i--)
		{
			a[i]+=b[i];
			if(a[i]>9)
			{
				a[i]%=10;
				a[i-1]++;
			}
		}
		printf("Case %d:n%s + %s = ",++x,d);
		for(i=(a[0]==0?1:0);i<=k;i++)
			printf("%d",a[i]);
		printf("n");
	}
	return 0;
}

模板：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<string>
using namespace std;
#define Max(a,sizeof(a))
class bign
{
    int len,s[222221];
    public:
    bign ()
    {
        mem(s,0);
        len=1;
    }
    string str() const
    {
        string res="";
        for(int i=0; i<len; i++)
            res=(char)(s[i]+'0')+res;
        if(res=="")
            res="0";
        return res;
    }
    bign operator = (const char* a)
    {
        len=strlen(a);
        for(int i=0; i<len; i++)
        {
            s[i]=a[len-i-1]-'0';
        }
        return *this;
    }
    bign operator = (int a)
    {
        char s[222221];
        sprintf(s,"%d",a);
        *this=s;
        return *this;
    }
    bign operator + (const bign& b) const
    {
        bign c;
        c.len=0;
        for(int i=0,g=0; g||i<max(len,b.len); i++)
        {
            int x=g;
            if(i<len) x+=s[i];
            if(i<b.len) x+=b.s[i];
            c.s[c.len++]=x%10;
            g=x/10;
        }
        return c;
    }
};
istream& operator >>(istream &in,bign& x)
{
    string s;
    in>>s;
    x=s.c_str();
    return in;
}
ostream& operator << (ostream &out,const bign& x)
{
    out<<x.str();
    return out;
}
int main()
{
    bign a,b;
    int n,i=1;
    cin>>n;
    while(n--)
    {
        cin>>a>>b;
        printf("Case %d:n",i++);
        cout<<a<<" + "<<b<<" = "<<a+b<<endl;
    }
    return 0;
}

A+B Problem IV

时间限制： 1000 ms ?|? 内存限制： 65535 KB

难度： 3

描述

acmj最近发现在使用计算器计算高精度的大数加法时很不方便，于是他想着能不能写个程序把这个问题给解决了。

输入

包含多组测试数据
每组数据包含两个正数A,B（可能为小数且位数不大于400）

输出

每组输出数据占一行，输出A+B的结果，结果需要是最简的形式。

样例输入

1.9 0.1
0.1 0.9
1.23 2.1
3 4.0

样例输出

强大的正则表达式;

import java.math.BigDecimal;
import java.util.Scanner;

public class Main{
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
while (cin.hasNext()) {
BigDecimal a = cin.nextBigDecimal();
BigDecimal b = cin.nextBigDecimal();
BigDecimal c = a.add(b);
System.out.println(sw(c.toString()));
}
}

static String sw(String s) {
if (s.indexOf(".") > 0) {
s = s.replaceAll("0+?$","");
s = s.replaceAll("[.]$","");
}
return s;
}
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!