BIGNUM spoj – Xử lý số nguyên lớn

Đặng Minh Tiến

Nguồn đề bài: BIGNUM

1. Đề bài BIGNUM spoj

Cho hai số nguyên dương A và B ( A & B có không quá 1000 chữ số )

Yêu cầu

Tính A + B, A – B, A * B
Khi kết quả là 0 các bạn phải in ra 0, nếu in -0 là sai
Các chữ số 0 không có nghĩa ở đầu không được in ra. VD 013 thì phải in ra là 13, chữ số 0 ở đầu không có nghĩa vì cách chấm ở đây là so sánh 2 FILE kết quả

Input

Dòng 1: số nguyên A
Dòng 2: số nguyên B

Output

Dòng 1: Kết quả A + B
Dòng 2: Kết quả A – B
Dòng 3: Kết quả A * B

Example

Input:

10
11

Output:

21
-1
110

2. Code tham khảo BIGNUM spoj

a. Code BIGNUM pascal

{$MODE OBJFPC}
 
 
Const
   digit=8;
   maxN=301;
   base=100000000;
 
 
Type
   BigNum=array[0..maxN] of Int64;
   ll=LongInt;
 
Var
   s1,s2,Res  : AnsiString;
   a1,a2      : BigNum;
   ex         : boolean;
 
 
Function max(a,b:Int64):Int64;
Begin
   if a>b then max:=a else max:=b;
End;
 
 
Procedure CoverBigNum(s:AnsiString;var a:BigNum);
Var
   sn,i,j: ll;
Begin
   Fillchar(a,sizeof(a),0);
   If s='0' then exit;
   sn:=(length(s)+digit-1) div digit;
   While length(s)<sn*digit do s:='0'+s;
   j:=length(s);
   a[0]:=sn;
   For i:=1 to sn do
      begin
         val(copy(s,j-digit+1,digit),a[i]);
         j:=j-digit;
      end;
End;
 
 
Procedure CoverNumBer(a:BigNum; Var Res: AnsiString);
Var
   s:AnsiString;
   i:ll;
Begin
   If a[0]=0 then
      begin
         res:='0';
         exit;
      end;
   res:='';
   For i:=1 to a[0] do
      begin
         str(a[i],s);
         while length(s)<digit do s:='0'+s;
         res:=s+res;
      end;
   While res[1]='0' do delete(res,1,1);
End;
 
 
Operator =(a,b: BigNum)bang: Boolean;
Var
   x,y: AnsiString;
Begin
   CoverNumBer(a,x);
   CoverNumBer(b,y);
   exit(x=y);
End;
 
 
Operator +(var a,b:BigNum)cong:BigNum;
Var
   i      :ll;
   num,nho:Int64;
Begin
   If (a[0]=0) or (b[0]=0) then
      begin
         If a[0]=0 then cong:=b
         else cong:=a;
         exit;
      end;
   cong[0]:=max(a[0],b[0]);
   nho:=0;
   For i:=1 to cong[0] do
      begin
         num:=a[i]+b[i]+nho;
         cong[i]:=num mod base;
         nho:=num div base;
      end;
   If nho>0 then
      begin
         Inc(cong[0]);
         cong[cong[0]]:=nho;
      end;
End;
 
 
Operator -(a,b:BigNum)tru:BigNum;
Var
   tmp: BigNum;
   i  :ll;
   num,nho:Int64;
Begin
   If a=b then
     begin
        FillChar(tru,SizeOf(tru),0);
        exit;
     end;
   If ex then
      begin
         tmp:=a;
         a:=b;
         b:=tmp;
      end;
   tru[0]:=max(a[0],b[0]);
   nho:=0;
   For i:=1 to tru[0] do
      begin
         num:=a[i]-b[i]-nho;
         If num<0 then
            begin
               nho:=1;
               num:=num+base;
            end
         else nho:=0;
         tru[i]:=num mod base;
      end;
End;
 
 
Operator *(a,b:BigNum)nhan:BigNum;
Var
   i,j:ll;
   x, nho:Int64;
   S: AnsiString;
Begin
   Fillchar(nhan,sizeof(nhan),0);
   If (a[0]=0) or (b[0]=0) then exit;
   nhan[0]:=a[0]+b[0]-1;
   For i:=1 to a[0] do
      For j:=1 to b[0] do
         nhan[i+j-1]:=nhan[i+j-1]+a[i]*b[j];
   nho:=0;
   For i:=1 to nhan[0] do
      begin
         x:=nhan[i]+nho;
         nho:=x div base;
         nhan[i]:=x mod base;
      end;
   If nho>0 then
      begin
         inc(nhan[0]);
         nhan[nhan[0]]:=nho;
      end;
End;
 
 
Procedure Enter;
Begin
  ReadLn(s1);
  ReadLn(s2);
  ex:=(length(s1)<length(s2)) or ((length(s1)=length(s2)) and (s1<s2));
End;
 
 
Procedure Main;
Var
   x:BigNum;
Begin
   CoverBigNum(s1,a1);
   CoverBigNum(s2,a2);
   CoverNumBer(a1+a2,Res);
   WriteLn(Res);
   CoverNumBer(a1-a2,Res);
   If ex then Write('-');
   WriteLn(Res);
   CoverNumBer(a1*a2,Res);
   WriteLn(Res);
End;
 
 
BEGIN
   Enter;
   Main;
END.

b. Code BIGNUM c++

#include<iostream>
#include<string>
using namespace std;

string add(string a, string b)
{
    string res="";
    while(a.length() < b.length()) a="0"+a;
    while(b.length() < a.length()) b="0"+b;
    int carry=0;
    for(int i=a.length()-1;i>=0;i--)
    {
        int tmp=a[i]-48 + b[i]-48 + carry;
        carry=tmp/10;
        tmp=tmp%10;
        res=(char)(tmp+48)+res;
    }
    if(carry>0) res="1"+res;
    return res;
}

string sub(string a, string b)
{
    string res="";
    while(a.length() < b.length()) a="0"+a;
    while(b.length() < a.length()) b="0"+b;
    bool neg=false;
    if(a<b)
    {
        swap(a,b);
        neg=true;
    }
    int borrow=0;
    for(int i=a.length()-1; i>=0;i--)
    {
        int tmp=a[i]-b[i]-borrow;
        if(tmp<0)
        {
            tmp+=10;
            borrow=1;
        }
        else borrow=0;
        res=(char)(tmp%10 + 48) + res;
    }
    while(res.length()>1 && res[0]=='0') res.erase(0,1);
    if(neg) res="-"+res;
    return res;
}

string mul(string a, string b)
{
    string res="";
    int n=a.length();
    int m=b.length();
    int len=n+m-1;
    int carry=0;
    for(int i=len;i>=0;i--)
    {
        int tmp=0;
        for(int j=n-1;j>=0;j--)
            if(i-j<=m && i-j>=1)
            {
                int a1=a[j]-48;
                int b1=b[i-j-1]-48;
                tmp+=a1*b1;
            }
            tmp+=carry;
            carry=tmp/10;
            res=(char)(tmp%10 + 48)+res;
    }
    while(res.length()>1 && res[0]=='0') res.erase(0,1);
    return res;
}
int main()
{
    //freopen("in.txt","r",stdin);
    string a, b;
    cin>>a>>b;
    cout<<add(a,b)<<endl;
    cout<<sub(a,b)<<endl;
    cout<<mul(a,b);
}

c. Code BIGNUM c++ tối ưu

Code này không dùng để submit lên spoj, nhưng bạn có thể dùng nó để xử lí các bài toán khác, nó rất tối ưu.

Mình xin phép chia sẻ lại của anh Nguyễn Tiến Trung Kiên

#include <stdio.h>
#include <assert.h>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

#define long long long
#define f1(i,n) for (int i=1; i<=n; i++)
#define f0(i,n) for (int i=0; i<n; i++)

typedef vector<int> vi;
const int BASE=10000;

void fix(vi &a){
    a.push_back(0);
    f0(i,a.size()-1) { 
        a[i+1]+=a[i]/BASE; a[i]%=BASE; 
        if (a[i]<0) { a[i]+=BASE; a[i+1]--; }
    }
    while (a.size()>=2 && a.back()==0) a.pop_back();
}

void operator += (vi &a, const vi &b) { 
    a.resize(max(a.size(), b.size()));
    f0(i,b.size()) a[i]+=b[i];
    fix(a);
}

vi operator * (const vi &a, const vi &b){
    vi c(a.size()+b.size());
    f0(i,a.size()) f0(j,b.size()) c[i+j]+=a[i]*b[j];
    return fix(c), c;
}

vi to_vi(int x) // x<BASE
    { return vi(1,x); }

void operator -= (vi &a, const vi &b)
    { f0(i,b.size()) a[i]-=b[i]; fix(a); }
void operator *= (vi &a, int x) // x<BASE
    { f0(i,a.size()) a[i]*=x; fix(a); }
vi operator + (vi a, const vi &b)
    { a+=b; return a; }
vi operator - (vi a, const vi &b)
    { a-=b; return a; }
vi operator * (vi a, int x) // x<BASE
    { a*=x; return a; }
    
bool operator < (const vi &a, const vi &b){
    if (a.size() != b.size()) return a.size()<b.size();
    for (int i=a.size()-1; i>=0; i--)
    if (a[i]!=b[i]) return a[i]<b[i];
    return false;
}

void divide(const vi &a, int x, vi &q, int &r) {
    q.clear(); r=0;
    for (int i=a.size()-1; i>=0; i--) {
        r=r*BASE+a[i];
        q.push_back(r/x); r%=x;
    }
    reverse(q.begin(), q.end());
    fix(q);
}

vi operator / (const vi &a, int x)
    { vi q; int r; divide(a, x, q, r); return q; }
int operator % (const vi &a, int x)
    { vi q; int r; divide(a, x, q, r); return r; }
    
istream& operator >> (istream& cin, vi &a){
    string s; cin >> s;
    a.clear(); a.resize(s.size()/4+1);
    f0(i,s.size()) {
        int x = (s.size()-1-i)/4; // <- log10(BASE)=4
        a[x]=a[x]*10+(s[i]-'0');
    }
    return fix(a), cin;
}

ostream& operator << (ostream& cout, const vi &a){
    printf("%d", a.back());
    for (int i=(int)a.size()-2; i>=0; i--)
    printf("%04d", a[i]);
    return cout;
}

void test_fib(int n){
    vi a=to_vi(1), b=to_vi(1);
    f1(i,n/2) {
        a+=b; b+=a;
        cout << "F[" << i*2+1 << "]=" << a << endl;
        cout << "F[" << i*2+2 << "]=" << b << endl;
    }
}

void test_fact(int n){
    vi P=to_vi(1);
    f1(i,n) {
        P*=i;
        cout << i << "!= " << P << endl;
    }
}

void test_divide(){
    vi a; int x;
    for (;;){
        cout << "Input a big integer and a small integer (<10000)" << endl;
        if (cin >> a >> x); else break;
        cout << "a=" << a << " x=" << x << endl;
        vi q=a/x; int r=a%x;
        cout << "a/x=" << q << "; a%x=" << r << endl;
        vi a0 = q*to_vi(x)+to_vi(r);
        assert(a0==a && !(a0<a) && !(a0>a));
    }
}

main(){
    cout << "Press Enter to run test_fib()" << endl;
    cin.ignore(1); test_fib(100);
    cout << "Press Enter to run test_fact()" << endl;
    cin.ignore(1); test_fact(100);
    cout << "Press Enter to run test_divide()" << endl;
    cin.ignore(1); test_divide();
}

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *