poj 1001 Exponentiation 高精度乘法 快速幂

缘起

学习大整数乘法以及乘幂. 但是使用的是朴素O(n^2)的算法(因为这里 幂次<=25, 所以就算O(n^2)也不会吃T).

分析

题意很裸

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
涉及计算非常大的幅度和精度的精确值的问题是常见的。 例如，国债的计算是许多计算机系统的征税经验。
这个问题要求你编写一个程序来计算R^n的精确值，其中R是实数（0.0 <R <99.999），n是一个整数，0 <n <= 
25。

【输入】
输入将由一组R和n的值组成。 R值将占据第1列到第6列，n值将在第8列和第9列中。

【输出】
输出将由每行输入的一行组成，给出R^n的精确值。 应在输出中抑制前导零。 不得打印无效的尾随零。 如果结
果是整数，则不要打印小数点。

【样例输入】
95.123 12
0.4321 20
5.1234 15
6.7592  9
98.999 10
1.0100 12

【样例输出】
548815620517731830194541.899025343415715973535967221869852721
.00000005148554641076956121994511276767154838481760200726351203835429763013462401
43992025569.928573701266488041146654993318703707511666295476720493953024
29448126.764121021618164430206909037173276672
90429072743629540498.107596019456651774561044010001
1.126825030131969720661201

【限制】
Time limit 500 ms
Memory limit 10000 kB

算法倒没什么，就是输入输出比较恶心. 要小心

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
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
#include "stdafx.h"

#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <algorithm>
#include <iomanip>
#include <vector>

#define LOCAL
typedef long long LL;

using namespace std;

class bigint // 大整数类
{
public:
	bigint(LL a) // 用long long新建bigint, 注意, long long 的范围是 10^19, 而且科学计数法的最高位还是9, 这就是为什么我们要选择long long 作为大整数的一节的原因. 因为做大整数乘法的时候 10^9*10^9=10^18 也不会超出long long 的范围
	{
		while(a) num.push_back(a%BASE),a/=BASE;
	}

	bigint(){};

	bigint(string s) // 用 字符串 构造大整数, 例如输入的字符串是 "1034004543543", 我们要将其存储为  004543543-->1034, 其中num[0]=004543543, num[1] = 1034
	{
		int n = s.length();
		for (int i = n-1; i>=0; i-=BASE_LEN) // 从高位开始构建
		{
			int j = max(0, i-BASE_LEN+1); // 则参与本次vector节点构建的字符是[j,...,i]
			LL t = 0;
			while(j<=i)
			{
				t = t*10+s[j]-'0'; // 洪特规则, 求出[j,...,i]表示的long long
				j++;
			}
			num.push_back(t);
		}
	}

	string toString() // 将大整数转为字符串输出(方便结果输出)
	{
		stringstream ss;
		bool flag = true; // 是否在输出vector的栈顶元素? (它是大整数的最高位部分)， 之所以要区分是因为栈顶元素是不能补0的
		while(!num.empty())
		{
			if (flag)
			{
				ss << num.back();
				flag = false;
			}
			else
			{
				ss << setw(BASE_LEN) << setfill('0') <<num.back(); // 熟练使用STL 能极大减少编码的复杂度(而且看上去会很优雅)
			}
			num.pop_back();
		}
		return ss.str();
	}

	static bigint add(const bigint &a, const bigint &b) // 大整数加法 a+b(a,b皆非负), 其实就是小学生加法, 复杂度是O(n)的, 比字符串版本的大整数加法要快, 因为这里使用BASE_LEN作为一节, 所以其实一次做9位数加法（而且long long相加很快）, 即常数优化的.效率更高
	{
		bigint ans;
		for (LL i =0, carry=0; ; i++) // 注意, 大整数的结构是 num 的栈顶元素存储高位, 所以要从低位相加, carry 是上一步相加结果的进位(即i-1)
		{
			if (!carry && i>=a.num.size() && i >= b.num.size()) break; // 如果a和b都没有弹药了, 而且上一步并没有发生进位
			if (i<a.num.size()) // 如果a还有弹药
			{
				carry += a.num[i];
			}
			if (i<b.num.size()) // 如果b还有弹药
			{
				carry += b.num[i];
			}
			ans.num.push_back(carry%BASE);
			carry /= BASE; // 作为a.num[i+1]和b.num[i+1]的进位
		}
		return ans;
	}

	static bigint substract(bigint &a, bigint &b) // 高精度减法 a-b, 这里假设 a>=b, 复杂度是 O(N)
	{
		bigint ans;
		unsigned int i; // 注意, 因为size() 返回的是无符号整数, 所以这里最好使用unsigned int
		for (i = 0; i<b.num.size();i++)
		{
			ans.num.push_back(a.num[i]-b.num[i]); // 可能为负值
		}
		for (; i<a.num.size();i++)
		{
			ans.num.push_back(a.num[i]); // 把a剩下的塞进去
		}
		for (i = 0; i<ans.num.size()-1;i++) // 从ans的低位开始扫描负值, 即处理小学生减法之借位
		{
			if (ans.num[i]<0)
			{
				ans.num[i]+=BASE;
				ans.num[i+1]--; // 借位
			}
		}
		while(!ans.num.back()) // 删除无意义的前导0
		{
			ans.num.pop_back();
		}
		return ans;
	}

	int cmp(const bigint &b) const // 大于b返回1, 等于b返回0,小于b返回-1
	{
		if (num.size() != b.num.size())
		{
			return num.size()< b.num.size()?-1:1;
		}
		for (int i = num.size()-1; ~i; i--)
		{
			if (num[i]!=b.num[i])
			{
				return num[i]<b.num[i]?-1:1;
			}
		}
		return 0;
	}

	static bigint multiply(const bigint &a, const bigint &b) // 非负大整数乘法 a*b 复杂度 O(n^2)
	{
		bigint ans(vector<LL>(a.num.size()+b.num.size(),0)); // m位*n位最多m+n位,最少m+n-1位
		for (unsigned int i = 0; i< a.num.size(); i++)
		{
			for (unsigned int j =0; j<b.num.size();j++)
			{
				ans.num[i+j]+=a.num[i]*b.num[j];  // ans[i+j]的来源不止一个, 例如 ans[3]可以是 a[1]*b[2]也可以是a[2]*b[1]
				ans.num[i+j+1]+=ans.num[i+j]/BASE; // 进位
				ans.num[i+j]%=BASE;
			}
		}
		while(!ans.num.empty() && !ans.num.back()) // 去掉无意义的前导0
		{
			ans.num.pop_back();
		}
		return ans;
	}

	static bigint pow(bigint &a, int &b) // 求a^b, b是整型(已经够大了)
	{
		bigint ans(vector<LL>(1,1)); // ans=1
		while(b) // 快速幂
		{
			if (b&1)
			{
				ans = multiply(ans, a);
			}
			if (b>1)
			{
				a = multiply(a,a);
			}
			b>>=1;
		}
		return ans;
	}

private:
	const static int BASE_LEN=9,BASE=1000000000;// 10亿为基数
	vector<LL> num; // 构建大整数是这样的, 比如1034004543543, 在我们的bigint类中存储为  004543543-->1034, num[0]=004543543, num[1] = 1034
	bigint(vector<LL> num):num(num){} //使用一个vector构建大整数
};


int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	freopen("d:\\my.out", "w", stdout);
#endif
	string a;
	int b;
	while(cin >> a >> b)
	{
		int pos = 0; // 最后结果小数点要左移动pos位
		bool flag = false; // 有没有越过前导0
		string aa;
		for (int i = 0; i<a.length();i++)
		{
			if (a[i]=='.')
			{
				pos = (5-i)*b;
			}
			else
			{
				if (a[i]!='0')
				{
					flag = true; // 已经越过前导零
					aa.push_back(a[i]);
				}
				else if (flag) // 是0 但是已经越过前导0了
				{
					aa.push_back(a[i]);
				}
				else // 是0 但是尚未越过前导0
				{
					continue;
				}
			}
		}
		bigint A(aa);
		string ans = bigint::pow(A, b).toString(); // 求出乘幂
		a.clear(); // a清空了用来装结果
		while(pos&&!ans.empty()&&ans.back()=='0') // 抵消pos来去掉ans尾部的0
		{
			pos--;
			ans.pop_back();
		}
		flag = pos; // 要不要加 .
		while(pos--) // 开始装入真正的结果了
		{
			if (!ans.empty())
			{
				a.push_back(ans.back());
				ans.pop_back();
			}
			else
			{
				a.push_back('0');
			}
		}
		if (flag)
		{
			a.push_back('.');
		}
		while (!ans.empty())
		{
			a.push_back(ans.back());
			ans.pop_back();
		}
		string ret(a.rbegin(), a.rend());
		cout << ret << endl;
	}
	return 0;
}

ac情况

影法师 Accepted 128kB 1ms 6115 B G++ 刚刚

这里顺便说一下，我是到百炼oj去提交的，老版的poj不支持 c++11. 导致我的代码编译报错.