Posted on 2010-11-30 14:53
Hero 阅读(449)
评论(0) 编辑 收藏 引用 所属分类:
代码如诗--ACM
1
//SGU 112 .CPP_VS Accepted 0 ms 0 kb
2![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
3
#include <iostream>
4
#include <cstdlib>
5
#include <string.h>
6
#include <string>
7![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
8
using namespace std ;
9
typedef long long llong ;
10![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
11
const int size = 200 ;
12
const int base = 100 ;
13
const int cap = 500 ;
14![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
15![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
struct Bigint
{
16
int len ; int data[cap] ;
17![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
18![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
Bigint():len(0)
{}
19![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
Bigint( int x ):len(0)
{//小整数赋值//
20
for( ; x>0; x/=base) data[len++] = x % base ;
21
}
22![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
Bigint( const Bigint &x ):len(x.len)
{//Bigint拷贝赋值//
23
memcpy( data, x.data, len*sizeof(data[0]) ) ;
24
}
25
Bigint &operator=( const Bigint x )
26![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
27
len = x.len ;
28
memcpy( data, x.data, len*sizeof(data[0]) ) ;
29
return *this ;
30
}
31![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
int &operator[]( int posi )
{
32
return data[posi] ;
33
}
34![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
int operator[]( int posi )const
{
35
return data[posi] ;
36
}
37
};
38![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
39
int cmp( const Bigint &A, const Bigint &B )
40![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
41
if( A.len != B.len ) return A.len > B.len ? 1 : - 1 ;
42
int i ; for( i=A.len-1; i>=0&&A[i]==B[i]; i-- ) ;
43![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
44
if( i < 0 ) return 0 ;//相等//
45
return A[i] > B[i] ? 1 : -1 ;
46
}
47![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
48
Bigint operator+( const Bigint &A, const Bigint &B )
49![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
50
int i ; int carry = 0 ; Bigint R ;
51
for( i=0; i<A.len||i<B.len||carry>0; i++ )
52![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
53
if( i < A.len ) carry += A[i] ;
54
if( i < B.len ) carry += B[i] ;
55
R[i] = carry % base ; carry = carry / base ;
56
}
57
R.len = i ; return R ;
58
}
59![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
60
Bigint operator-( const Bigint &A, const Bigint &B )
61![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
62
int i ; int carry = 0 ; Bigint R ;
63
R.len = A.len ;
64
for( i=0; i<R.len; i++ )
65![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
66
R[i] = A[i] - carry ; if( i < B.len ) R[i] -= B[i] ;
67![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if( R[i] < 0 )
{ carry = 1 ; R[i] += base ; }
68
else carry = 0 ;
69
}
70
while( R.len>0&&0==R[R.len-1] ) R.len-- ;//消除相减导致的前缀0
71![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
72
return R ;
73
}
74![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
75
Bigint operator*( const Bigint &A, const int &B )
76![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
77
int i ; llong carry = 0 ; Bigint R ;
78
for( i=0; i<A.len||carry>0; i++ )
79![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
80
if( i<A.len ) carry += (llong)(A[i])*B ;
81
R[i] = carry % base ; carry = carry / base ;
82
}
83
R.len = i ; return R ;
84
}
85
Bigint operator/( const Bigint &A, const int &B )
86![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
87
int i ; llong carry = 0 ; Bigint R ;
88
for( i=A.len-1; i>=0; i-- )
89![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
90
carry += A[i] ;
91
R[i] = carry / B ;
92
carry = carry - R[i]*B ; carry = carry * base ;
93
}
94
R.len = A.len ; while( R.len>0&&0==R[R.len-1] ) R.len-- ;//消除前缀0
95![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
96
return R ;
97
}
98
llong mod( const Bigint &A, const int &B )
99![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
100
int i ; llong carry = 0 ;
101
for( i=A.len-1; i>=1; i-- )
102![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
103
carry += A[i] ; carry = carry % B ; carry *= base ;
104
}
105
carry = carry + A[i] ; carry = carry % B ;
106![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
107
return carry ;
108
}
109![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
110
istream &operator>>( istream &in, Bigint &x )
111![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
112
char ch ;
113
for( x=0; in>>ch; )
114![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
115
x = x*10 + (ch-'0') ;
116
if( in.peek() <= ' ' ) break ;//注意是空格//
117
}
118
return in ;
119
}
120
ostream &operator<<( ostream &out, const Bigint &x )
121![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
122
out << ( 0==x.len ? 0 : x[x.len-1] ) ;
123
for( int i=x.len-2; i>=0; i-- )
124
for( int j=base/10; j>0; j/=10 )
125
out << x[i]/j%10 ;
126![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
127
return out ;
128
}
129![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
130
void mytostr( string &str, const Bigint &x )
131![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
132
str.clear() ; char temp[15] ;
133
if( 0 == x.len ) str += '0' ;
134
else
135![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
136
sprintf( temp, "%d", x[x.len-1] ) ;
137
str += temp ;
138![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
139
//int len = strlen(temp) ;
140
//for( int i=0; i<len; i++ ) str += temp[i] ;
141
}
142![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
143
for( int i=x.len-2; i>=0; i-- )
144
for( int j=base/10; j>0; j/=10 )
145
str += char(x[i]/j%10+'0') ;
146![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
147
str.reserve() ;
148
}
149![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
150
int main()
151![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
152
int ina, inb;
153
Bigint Bint0( 0 ) ;
154
Bigint Bint1( 1 ) ;
155![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
156
while( cin >> ina >> inb )
157![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
158
Bigint A(1);
159
for( int i=1; i<=inb; i++ )
160![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
161
A = A * ina;
162
}
163![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
164
Bigint B(1);
165
for( int i=1; i<=ina; i++ )
166![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
167
B = B * inb;
168
}
169![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
170
if( cmp(A, B) >=0 )
171![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
172
cout << A-B << endl;
173
}
174
else
175![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
176
cout << "-" << B-A << endl;
177
}
178
}
179![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
180
return 0 ;
181
}
182![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)