快速幂升级版
[题目描述]
给你两个正整数 a 和 b , 已知 a 的位数在 100 以内, b 的大小不超过 100.(注: 整数 12345 的位数是 5 位, 这意味着 a 可能会很大, 反正用 int 是存不了的).
请求出 a 的 b 次方的大小.
[输入格式]
输入一行包含两个正整数 a 和 b (a 的位数在 100 以内, b 的大小不超过 100), 以一个空格分隔.
[输出格式]
输出 a 的 b 次方的完整结果.
[样例输入]
1001 5
[样例输出]
1005010010005001
[题目分析]
这道题目考的知识点包括:
1, 高精度乘法;
2, 快速幂.
当然, 这道题目因为我数据量控制的比较小, 所以你直接使用高精度乘法进行运算 + 一个 for 循环也是可以做的.
但是快速幂实现起来更优.
直接使用高精度乘法进行计算的代码如下:
- #include <bits/stdc++.h>
- using namespace std;
- const int maxn = 100010;
- int a[maxn], b[maxn], res[maxn];
- string multi(string s1, string s2) { // under condition: s1,s2>=0
- // 初始化部分
- int n = s1.length(), m = s2.length();
- for (int i = 0; i <n; i ++) a[i] = s1[n-1-i] - '0';
- for (int i = 0; i < m; i ++) b[i] = s2[m-1-i] - '0';
- int len = n + m;
- for (int i = n; i < len; i ++) a[i] = 0;
- for (int i = m; i < len; i ++) b[i] = 0;
- for (int i = 0; i < len; i ++) res[i] = 0;
- // 处理部分
- for (int i = 0; i < n; i ++)
- for (int j = 0; j < m; j ++)
- res[i+j] += a[i] * b[j];
- for (int i = 0; i < len; i ++) {
- res[i+1] += res[i] / 10;
- res[i] %= 10;
- }
- // 返回部分
- int i = len-1;
- while (res[i] == 0 && i> 0) i --;
- string s = "";
- for (; i>= 0; i --) {
- char c = (char) (res[i] + '0');
- s += c;
- }
- return s;
- }
- string A, s;
- int B;
- int main() {
- cin>> A>> B;
- s = A;
- for (int i = 1; i <B; i ++) s = multi(s, A);
- cout << s << endl;
- return 0;
- }
使用高精度乘法 + 快速幂进行计算的代码如下:
- #include <bits/stdc++.h>
- using namespace std;
- const int maxn = 100010;
- int a[maxn], b[maxn], res[maxn];
- string multi(string s1, string s2) { // under condition: s1,s2>=0
- // 初始化部分
- int n = s1.length(), m = s2.length();
- for (int i = 0; i <n; i ++) a[i] = s1[n-1-i] - '0';
- for (int i = 0; i < m; i ++) b[i] = s2[m-1-i] - '0';
- int len = n + m;
- for (int i = n; i < len; i ++) a[i] = 0;
- for (int i = m; i < len; i ++) b[i] = 0;
- for (int i = 0; i < len; i ++) res[i] = 0;
- // 处理部分
- for (int i = 0; i < n; i ++)
- for (int j = 0; j < m; j ++)
- res[i+j] += a[i] * b[j];
- for (int i = 0; i < len; i ++) {
- res[i+1] += res[i] / 10;
- res[i] %= 10;
- }
- // 返回部分
- int i = len-1;
- while (res[i] == 0 && i> 0) i --;
- string s = "";
- for (; i>= 0; i --) {
- char c = (char) (res[i] + '0');
- s += c;
- }
- return s;
- }
- string A, s;
- int B;
- string solve(string a, int b) {
- if (b == 0) return "1";
- if (b == 1) return a;
- string tmp = solve(a, b/2);
- tmp = multi(tmp, tmp);
- if (b % 2) tmp = multi(tmp, a);
- return tmp;
- }
- int main() {
- cin>> A>> B;
- cout << solve(A, B) << endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3109888.html