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

Nguồn đề bài: BIGNUM

Nội dung bài viết

1. Đề bài BIGNUM spoj
2. Code tham khảo BIGNUM spoj

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.

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

{$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);
}

#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();
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

#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();

}

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

1. Đề bài BIGNUM spoj

Yêu cầu

Input

Output

Example

2. Code tham khảo BIGNUM spoj

a. Code BIGNUM pascal

b. Code BIGNUM c++

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

Bài viết liên quan

Trả lời Hủy