解题思路: 高精度模拟大数乘法,快速幂算法减小复杂度
注意事项: 建议使用结构体,主函数更清晰
参考代码:
#include <iostream> // #include <sstream> // #include <cstdio> // #include <algorithm> // #include <cmath> // #include <cstdlib> #include <cstring> // #include <cctype> // #include <string> // #include <climits> // #include <map> // #include <vector> // #include <list> // #include <set> using namespace std; const int maxn = 1004; // const long long MOD = 100000007; // const double PI = acos(-1.0); const int base = 2; // 乘方底数 struct bigNum { int num[ maxn ]; // 倒序存储,num[i]代表base^num[i] int len; bigNum( int digit ) { // 可以设置一个0~9的初始数字 memset(num, 0, sizeof(num)); num[0] = digit; len = 1; } bigNum( bigNum &other ) { // copy 拷贝构造函数 memcpy(num, other.num, maxn * sizeof (int)); len = other.len; } void settle() { // 整理数字,使每一位都在0~9范围内;使len为长度 int i; for (i = 0; i < len || num[i]; i++) { if (num[i] >= 10) { num[i + 1] += num[i] / 10; num[i] %= 10; } } len = i; while (num[len - 1] == 0) len--; } void mul_bigNum( bigNum &mul ) { // this.num *= mul.num int temp[ maxn ]; memset(temp, 0, sizeof(num)); for (int i = 0; i < len; i++) for (int j = 0; j < mul.len; j++) temp[i + j] += num[i] * mul.num[j]; memcpy(num, temp, maxn * sizeof (int)); settle(); } void mul_bigNum_self() { // this.num *= this.num bigNum temp(*this); mul_bigNum( temp ); } void output() { // 输出 for (int i = len - 1; i >= 0; i--) cout << num[i]; cout << endl; } }; bigNum ans(1), m(base); int main() { int n; cin >> n; while (n) { if (n & 1) ans.mul_bigNum( m ); n >>= 1; m.mul_bigNum_self(); } ans.output(); return 0; }
0.0分
1 人评分
C二级辅导-统计字符 (C语言代码)浏览:506 |
矩形面积交 (Java代码)浏览:1220 |
C语言训练-排序问题<2> (C++代码)浏览:886 |
C语言程序设计教程(第三版)课后习题6.1 (C语言代码)浏览:520 |
C语言程序设计教程(第三版)课后习题7.4 (C语言代码)浏览:606 |
【出圈】 (C语言代码)浏览:558 |
C语言程序设计教程(第三版)课后习题10.5 (C语言代码)浏览:552 |
淘淘的名单 (C语言代码)答案错误???浏览:595 |
C语言程序设计教程(第三版)课后习题6.6 (C语言代码)浏览:624 |
C语言训练-求PI* (C语言代码)浏览:614 |