02/10/2018, 13:58
BIGNUM spoj – Xử lý số nguyên lớ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 ...
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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 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. |
