Posted on 2010-11-30 14:53
Hero 閱讀(485)
評論(0) 編輯 收藏 引用 所屬分類:
代碼如詩－－ACM
1
//SGU 112 .CPP_VS Accepted 0 ms 0 kb
2
3#include <iostream>
4#include <cstdlib>
5#include <string.h>
6#include <string>
7
8using namespace std ;
9typedef long long llong ;
10
11const int size = 200 ;
12const int base = 100 ;
13const int cap = 500 ;
14
15
struct Bigint 
{
16
int len ; int data[cap] ;
17
18
Bigint():len(0) {}
19 Bigint( int x ):len(0) {//小整數賦值//
20 for( ; x>0; x/=base) data[len++] = x % base ;
21
}
22 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 {
27 len = x.len ;
28 memcpy( data, x.data, len*sizeof(data[0]) ) ;
29 return *this ;
30 }
31 int &operator[]( int posi ) {
32 return data[posi] ;
33 }
34 int operator[]( int posi )const {
35 return data[posi] ;
36 }
37
};
38
39int cmp( const Bigint &A, const Bigint &B )
40{
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
44 if( i < 0 ) return 0 ;//相等//
45 return A[i] > B[i] ? 1 : -1 ;
46}
47
48Bigint operator+( const Bigint &A, const Bigint &B )
49{
50 int i ; int carry = 0 ; Bigint R ;
51 for( i=0; i<A.len||i<B.len||carry>0; i++ )
52 {
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
60Bigint operator-( const Bigint &A, const Bigint &B )
61{
62 int i ; int carry = 0 ; Bigint R ;
63 R.len = A.len ;
64 for( i=0; i<R.len; i++ )
65 {
66 R[i] = A[i] - carry ; if( i < B.len ) R[i] -= B[i] ;
67 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
72 return R ;
73}
74
75Bigint operator*( const Bigint &A, const int &B )
76{
77 int i ; llong carry = 0 ; Bigint R ;
78 for( i=0; i<A.len||carry>0; i++ )
79 {
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}
85Bigint operator/( const Bigint &A, const int &B )
86{
87 int i ; llong carry = 0 ; Bigint R ;
88 for( i=A.len-1; i>=0; i-- )
89 {
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
96 return R ;
97}
98llong mod( const Bigint &A, const int &B )
99{
100 int i ; llong carry = 0 ;
101 for( i=A.len-1; i>=1; i-- )
102 {
103 carry += A[i] ; carry = carry % B ; carry *= base ;
104 }
105 carry = carry + A[i] ; carry = carry % B ;
106
107 return carry ;
108}
109
110istream &operator>>( istream &in, Bigint &x )
111{
112 char ch ;
113 for( x=0; in>>ch; )
114 {
115 x = x*10 + (ch-'0') ;
116 if( in.peek() <= ' ' ) break ;//注意是空格//
117 }
118 return in ;
119}
120ostream &operator<<( ostream &out, const Bigint &x )
121{
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
127 return out ;
128}
129
130void mytostr( string &str, const Bigint &x )
131{
132 str.clear() ; char temp[15] ;
133 if( 0 == x.len ) str += '0' ;
134 else
135 {
136 sprintf( temp, "%d", x[x.len-1] ) ;
137 str += temp ;
138
139 //int len = strlen(temp) ;
140 //for( int i=0; i<len; i++ ) str += temp[i] ;
141 }
142
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
147 str.reserve() ;
148}
149
150int main()
151{
152 int ina, inb;
153 Bigint Bint0( 0 ) ;
154 Bigint Bint1( 1 ) ;
155
156 while( cin >> ina >> inb )
157 {
158 Bigint A(1);
159 for( int i=1; i<=inb; i++ )
160 {
161 A = A * ina;
162 }
163
164 Bigint B(1);
165 for( int i=1; i<=ina; i++ )
166 {
167 B = B * inb;
168 }
169
170 if( cmp(A, B) >=0 )
171 {
172 cout << A-B << endl;
173 }
174 else
175 {
176 cout << "-" << B-A << endl;
177 }
178 }
179
180 return 0 ;
181}
182