大数

大数

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
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
190
191
192
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>
using namespace std;
//大数类
class bigInteger{
public:
int digit[1000]; //使用digit数组,保存大数中的每一位,暂且每4位一个单元
int size; //size表示第一个还没使用的数组单元的编号
//初始化结构体
bigInteger(){
size = 0;
memset(digit,0,sizeof(digit));
}
bigInteger(const string); //通过string类型构造大数
bigInteger(int); //通过int类型构造大数
bigInteger operator+(const bigInteger &) const; //两个大数之间的相加运算
bigInteger operator-(const bigInteger &) const; //两个大数之间的相减运算
bigInteger operator*(int x) const; //两个大数之间的相乘运算
bigInteger operator/(int x) const; //两个大数之间的相除运算
int operator%(int x) const; //两个大数之间的取余运算
bool is_zero();
void print();

};


bigInteger::bigInteger(const string str) {
size = 0;
memset(digit,0,sizeof(digit));
int length = (int) str.length();
for (int i = length-1,j=0,t=0,c=1; i >=0 ; --i) {
t+=(str[i]-'0')*c;
j++;
c*=10;
if (j==4||i==0){
digit[size++] = t;
j = 0;
t = 0;
c = 1;
}
}
}

bigInteger::bigInteger(int x) {
size = 0;
memset(digit,0,sizeof(digit));
if (x){
while (x){
digit[size++] = x%10000;
x = x/10000;
}
}
}

bigInteger bigInteger::operator+(const bigInteger &A) const {
bigInteger ret;
int carry = 0;
for (int i = 0; i < A.size || i<size; ++i) {
int tmp = A.digit[i]+digit[i]+carry;
carry = tmp/10000;
tmp %= 10000;
ret.digit[ret.size++]=tmp;
}
if (carry!=0){
ret.digit[ret.size++] = carry;
}
return ret;
}

bigInteger bigInteger::operator-(const bigInteger &A) const {
//这里一定是A比较小,不会减出负数
bigInteger ret;
int carry = 0;
for (int i = 0; i<size; ++i) {
int real_num = digit[i]-carry;
if (real_num<A.digit[i]){
real_num = real_num + 10000;
carry = 1;
}
ret.digit[ret.size++] = real_num-A.digit[i];
}
int i = size-1;
for (; i >=0 ; --i) {
if (ret.digit[i]!=0){
break;
}
}
if (i<0){
ret.size = 1;
ret.digit[0] = 0;
} else
ret.size = i+1;
return ret;
}

bigInteger bigInteger::operator*(int x) const {
bigInteger ret;
int carry = 0;
for (int i = 0; i <size ; ++i) {
int tmp = x*digit[i]+carry;
carry = tmp/10000;
tmp%=10000;
ret.digit[ret.size++] = tmp;
}
if (carry!=0){
ret.digit[ret.size++] = carry;
}
return ret;
}

bigInteger bigInteger::operator/(int x) const {
bigInteger ret;
int remainder = 0;
for (int i = size-1; i >=0 ; --i) {
int tmp = digit[i]+10000*remainder;
ret.digit[i] = tmp/x;
remainder = tmp%x;
}
for (int i = 0; i < 1000; ++i) {
if (digit[i]!=0)
ret.size = i;
}
ret.size++;
return ret;
}

int bigInteger::operator%(int x) const {
int remainder = 0;
for (int i = size-1; i >=0 ; --i) {
int tmp = digit[i]+10000*remainder;
remainder = tmp%x;
}
return remainder;
}

void bigInteger::print() {
printf("%d",digit[size-1]);
for (int i = size-2; i >=0 ; --i) {
printf("%04d",digit[i]);
}
printf("\n");
}

bool bigInteger::is_zero() {
if (size==1&&digit[0]==0){
return true;
}
return false;
}

bigInteger change_to_10_base(string str,int m){
bigInteger ret = bigInteger(0);
bigInteger temp = bigInteger(1);
int length = str.length();
for (int i = length-1,c=1; i >=0; --i) {
int tmp = 0;
if (isdigit(str[i]))
tmp = str[i]-'0';
else
tmp = str[i]-'A'+10;
ret = ret+temp*tmp;
temp = temp*m;
}
return ret;
}


string change_to_m_base(bigInteger big_number , int m){
string ret="";
do {
int t = big_number % m;
if (t >= 10)
ret += (t - 10 + 'a');
else
ret += (t + '0');
big_number = big_number / m;
}while (!big_number.is_zero());
reverse(ret.begin(),ret.end());
return ret;
}

int main(){
int m,n;
string str;
while (cin>>m>>n>>str){
bigInteger from_m_base = change_to_10_base(str,m);
string s = change_to_m_base(from_m_base,n);
cout<<s<<endl;
}
}