Nguồn đề bài: BIGNUM
Nội dung bài viết
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
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. |
b. Code BIGNUM c++
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 | #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
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 | #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(); } |
Bài viết liên quan
- [CF490C] HACKING CYPHER, P151PROF spoj Cipher
- PTIT123E PTIT spoj – Số vòng
- NKABD spoj – Số phong phú
- lời giải LATGACH spoj – Lát gạch
- P167PROE spoj PTIT – ROUND 7E – Phương trình
- PTIT016E spoj PTIT – ACM PTIT 2016 E – Kỳ thi ACM/ICPC
- PTIT016D spoj PTIT- ACM PTIT 2016 D – Biểu thức
- Spoj PTIT PTIT016C – ACM PTIT 2016 C – Chẵn lẻ
- PTIT127A spoj PTIT – Tổ chức kì thi
- P167PROD spoj PTIT – ROUND 7D – ABC