1 /* 优点：
2 1 支持负整数的运算
3 2 良好的输出形式 没有前导零
4 3 支持cin直接输入 支持cout直接输出
5 4 支持整数的直接赋值 big_int x=100;
6 缺点：
7 1 封装不好 基本都是友元函数操作
8 2 速度慢 乘法没有使用FFT 除法采用二分法
9 使用STL string储存数据也造成速度不是很快
10 3 待解决的问题 不能直接输出 cout<<a-b
11 */
12
13 #include <iostream>
14 #include <algorithm>
15 #include <stack>
16 using namespace std;
17 void change (string &s) {
18 string tmp="";
19 int i;
20 for (i=0;i<s.size();i++)
21 if (s[i]!='0')
22 break;
23 if (i==s.size()) s="0";
24 else {
25 for (;i<s.size();i++)
26 tmp+=s[i];
27 s=tmp;
28 }
29 }
30 class big_int
31 {
32 private :
33 bool flag;
34 string s;
35 public :
36 big_int (){ flag=1; s="0"; }
37 big_int (int x);
38 bool operator ==(const big_int& x) {
39 string tmp=x.s;
40 change (s);
41 change (tmp);
42 if (x.s=="0"&&s=="0") return true;
43 return x.flag==flag&&s==tmp;
44 }
45 friend big_int operator+(const big_int& a, const big_int& b );
46 friend big_int operator-(const big_int& a, const big_int& b );
47 friend big_int operator*(const big_int& a, const big_int& b);
48 friend big_int operator/(const big_int& a, const big_int& b);
49 friend big_int operator%(const big_int& a, const big_int& b);
50 friend ostream& operator<<(ostream& out,big_int& x) {
51 if (!x.flag&&x.s!="0") cout<<"-";
52 change (x.s);
53 cout<<x.s;
54 return out;
55 }
56 friend istream& operator>>(istream& in,big_int& x) {
57 string tmp;
58 cin>>tmp;
59 if (tmp[0]=='-') {
60 x.flag=0;
61 x.s=tmp.substr(1,tmp.size()-1);
62 }
63 else {
64 x.flag=1;
65 x.s=tmp;
66 }
67 return in;
68 }
69 };
70 big_int:: big_int (int x) {
71 if (x<0) flag=0;
72 else flag=1;
73 x=abs(x);
74
75 s=""; string tmp="0";
76 if (x==0) s+=tmp;
77 while (x!=0) {
78 tmp[0]='0'+x%10;
79 s+=tmp;
80 x/=10;
81 }
82 reverse(s.begin(),s.end());
83 }
84 string add(string s1,string s2) {
85 reverse(s1.begin(),s1.end());
86 reverse(s2.begin(),s2.end());
87 int len =max (s1.size(),s2.size());
88 int k=0; int t1,t2;
89 string ans=""; string tmp="0";
90 for (int i=0;i<len;i++) {
91 t1=t2=0;
92 if (i<s1.size()) t1=s1[i]-'0';
93 if (i<s2.size()) t2=s2[i]-'0';
94 int t=t1+t2+k;
95 tmp[0]='0'+t%10; k=t/10;
96 ans+=tmp;
97 }
98 if (k!=0) {
99 tmp[0]='0'+k;
100 ans+=tmp;
101 }
102 reverse(ans.begin(),ans.end());
103 return ans;
104 }
105 string sub (string s1,string s2) {
106 reverse(s1.begin(),s1.end());
107 reverse(s2.begin(),s2.end());
108 int len =s1.size();
109 int t1,t2;
110 string ans=""; string tmp="0";
111 for (int i=0;i<len;i++) {
112 t1=s1[i]-'0'; t2=0;
113 if (i<s2.size()) t2=s2[i]-'0';
114 if (t1<t2) {
115 for (int j=i+1;j<len;j++)
116 if (s1[j]-'0'==0) s1[j]='9';
117 else {
118 s1[j]--;
119 break;
120 }
121 t1+=10;
122 }
123 tmp[0]=t1-t2+'0';
124 ans+=tmp;
125 }
126 reverse(ans.begin(),ans.end());
127 change(ans);
128 return ans;
129 }
130 bool m_cmp (string s1, string s2) {
131 change (s1);
132 change (s2);
133 if (s1.size()==s2.size()) {
134 for (int i=0;i<s1.size();i++)
135 if (s1[i]!=s2[i])
136 return s1[i]>s2[i];
137 }
138 return s1.size()>s2.size();
139 }
140 string s_mul (string s,int x,int k) {
141 string ans=""; string tmp="0";
142 for (int i=1;i<=k;i++) ans+=tmp;
143 k=0;
144 for (int i=0;i<s.size();i++) {
145 int t=s[i]-'0';
146 int p=t*x+k;
147 tmp[0]='0'+p%10; ans+=tmp;
148 k=p/10;
149 }
150 if (k) {
151 tmp[0]='0'+k;
152 ans+=tmp;
153 }
154 reverse(ans.begin(),ans.end());
155 change(ans);
156 return ans;
157 }
158 string mul (string s1,string s2) {
159 reverse(s1.begin(),s1.end());
160 reverse(s2.begin(),s2.end());
161 string ans="0";
162 for (int i=0;i<s2.size();i++) {
163 int x=s2[i]-'0';
164 string tmp=s_mul (s1,x,i);
165 ans=add(ans,tmp);
166 //cout<<ans<<endl;
167 }
168 return ans;
169 }
170 big_int operator+(const big_int& a, const big_int& b ) {
171 big_int c;
172 int t=a.flag^b.flag;
173 if (t==0) {
174 c.s=add (a.s,b.s);
175 c.flag=a.flag;
176 }
177 else {
178 if (m_cmp(a.s,b.s)) {
179 c.flag=a.flag;
180 c.s=sub (a.s,b.s);
181 }
182 else {
183 c.flag=b.flag;
184 c.s=sub (b.s,a.s);
185 }
186 }
187 return c;
188 }
189 big_int operator-(const big_int& a, const big_int& b ) {
190 big_int c=b;
191 c.flag=!b.flag;
192 return a+c;
193 }
194 big_int operator*(const big_int& a, const big_int& b) {
195 big_int c;
196 int t=a.flag^b.flag;
197 if (t) c.flag=0;
198 if (m_cmp(a.s,b.s)) c.s=mul (a.s,b.s);
199 else c.s=mul (b.s,a.s);
200 return c;
201 }
202 big_int operator/(const big_int& a, const big_int& b) {
203 if (b.s=="0") {
204 cout<<"error"<<endl;
205 exit(-1);
206 }
207 big_int c;
208 big_int _a=a, _b=b;
209 _a.flag=_b.flag=1;
210 if (m_cmp(_b.s,_a.s)) return c;
211
212 stack <big_int> q;
213 big_int k=1;
214 while (1) {
215 big_int x=k*_b; q.push(k);
216 if (m_cmp(x.s,_a.s))
217 break;
218 k=k*2;
219 }
220 big_int tmp=_a;
221 while (tmp.s!="0"&&!q.empty()) {
222 k=q.top(); q.pop();
223 big_int x=k*_b;
224 if ( !m_cmp(x.s,tmp.s)) {
225 tmp=tmp-x;
226 c=c+k;
227 }
228 }
229 if (a.flag^b.flag) c.flag=0;
230 return c;
231 }
232 big_int operator%(const big_int& a, const big_int& b) {
233 big_int c=a/b;
234 c=c*b;
235 c=a-c;
236 return c;
237 }
238 int main ()
239 {
240 big_int a,b;
241 big_int c=-100;
242 cout<<c<<endl;
243 while (cin>>a>>b) {
244 c=a+12;
245 cout<<c<<" ";
246 c=a-b;
247 cout<<c<<" ";
248 c=a*b;
249 cout<<c<<" ";
250 c=a/b;
251 cout<<c<<" ";
252 c=a%b;
253 cout<<c<<endl;
254 }
255 return 0;
256 }
