hdu1042

我不是女神ヾ 2022-01-15 10:09 155阅读 0赞

[为什么80%的码农都做不了架构师？>>> ][80_]  ![hot3.png][]

向牛人看起！[http://acm.hdu.edu.cn/showproblem.php?pid=1042][http_acm.hdu.edu.cn_showproblem.php_pid_1042]

摘自：[http://www.cnblogs.com/phinecos/archive/2009/10/06/1578411.html][http_www.cnblogs.com_phinecos_archive_2009_10_06_1578411.html]

#include<iostream> #include<stdio.h> #include<string> #include<iomanip> #include<algorithm> using namespace std; #include "time.h" const int MAX_GROUPS = 20000;//最多2万组，每组最多4位整数，即最多可容纳8万位整数 const int MAXN = 9999;//每组的上限值 const int GROUP_LEN = 4;//每组的最大长度 class BigInteger { private: int data[MAX_GROUPS]; int len; void init() { memset(data,0,sizeof(data)); } public: BigInteger() { init(); len = 0; } BigInteger(const int b); BigInteger(const BigInteger &); bool operator > (const BigInteger&)const; BigInteger & operator=(const BigInteger &); BigInteger & add(const BigInteger &); BigInteger & sub(const BigInteger &); BigInteger operator+(const BigInteger &) const; BigInteger operator-(const BigInteger &) const; BigInteger operator*(const BigInteger &) const; BigInteger operator/(const int &) const; void print(); }; BigInteger::BigInteger(const int num) { int res,tmp = num; len = 0; init(); while(tmp > MAXN) { res = tmp - tmp / (MAXN + 1) * (MAXN + 1); tmp = tmp / (MAXN + 1); data[len++] = res; } data[len++] = tmp; } BigInteger::BigInteger(const BigInteger & rhs) : len(rhs.len) { int i; init(); for(i = 0 ; i < len ; i++) { data[i] = rhs.data[i]; } } bool BigInteger::operator > (const BigInteger &rhs)const { int ln; if(len > rhs.len) { return true; } else if(len < rhs.len) { return false; } else if(len == rhs.len) { ln = len - 1; while(data[ln] == rhs.data[ln] && ln >= 0) { ln--; } if(ln >= 0 && data[ln] > rhs.data[ln]) { return true; } else { return false; } } } BigInteger & BigInteger::operator = (const BigInteger &rhs) { init(); len = rhs.len; for(int i = 0 ; i < len ; i++) { data[i] = rhs.data[i]; } return *this; } BigInteger& BigInteger::add(const BigInteger &rhs) { int i,nLen; nLen = rhs.len > len ? rhs.len : len; for(i = 0 ; i < nLen ; i++) { data[i] = data[i] + rhs.data[i]; if(data[i] > MAXN) { data[i + 1]++; data[i] = data[i] - MAXN - 1; } } if(data[nLen] != 0) { len = nLen + 1; } else { len = nLen; } return *this; } BigInteger & BigInteger::sub(const BigInteger &rhs) { int i,j,nLen; if (len > rhs.len) { for(i = 0 ; i < nLen ; i++) { if(data[i] < rhs.data[i]) { j = i + 1; while(data[j] == 0) j++; data[j]--; --j; while(j > i) { data[j] += MAXN; --j; } data[i] = data[i] + MAXN + 1 - rhs.data[i]; } else { data[i] -= rhs.data[i]; } } len = nLen; while(data[len - 1] == 0 && len > 1) { --len; } } else if (len == rhs.len) { for(i = 0 ; i < len ; i++) { data[i] -= rhs.data[i]; } while(data[len - 1] == 0 && len > 1) { --len; } } return *this; } BigInteger BigInteger::operator+(const BigInteger & n) const { BigInteger a = *this; a.add(n); return a; } BigInteger BigInteger::operator-(const BigInteger & T) const { BigInteger b = *this; b.sub(T); return b; } BigInteger BigInteger::operator * (const BigInteger &rhs) const { BigInteger result; int i,j,up; int temp,temp1; for(i = 0; i < len; i++) { up = 0; for(j = 0; j < rhs.len; j++) { temp = data[i] * rhs.data[j] + result.data[i + j] + up; if(temp > MAXN) { temp1 = temp - temp / (MAXN + 1) * (MAXN + 1); up = temp / (MAXN + 1); result.data[i + j] = temp1; } else { up = 0; result.data[i + j] = temp; } } if(up != 0) { result.data[i + j] = up; } } result.len = i + j; while(result.data[result.len - 1] == 0 && result.len > 1) result.len--; return result; } BigInteger BigInteger::operator/(const int & b) const { BigInteger ret; int i,down = 0; for(i = len - 1 ; i >= 0 ; i--) { ret.data[i] = (data[i] + down * (MAXN + 1)) / b; down = data[i] + down * (MAXN + 1) - ret.data[i] * b; } ret.len = len; while(ret.data[ret.len - 1] == 0) ret.len--; return ret; } void BigInteger::print() { int i; cout << data[len - 1]; for(i = len - 2 ; i >= 0 ; i--) { cout.width(GROUP_LEN); cout.fill('0'); cout << data[i]; } cout << endl; } int main() { clock_t start, finish; double duration; int i,n; BigInteger result,num; scanf("%d",&n); start = clock(); result = BigInteger(1); for(i = 2;i <= n; ++i) { num = BigInteger(i); result = result * num; } result.print(); finish = clock(); duration = (double)(finish - start) / CLOCKS_PER_SEC; printf( "%f seconds\n", duration ); return 0; }

转载于:https://my.oschina.net/garyun/blog/602958

[80_]: https://my.oschina.net/u/2663968/blog/3051541
[hot3.png]: /images/20220115/d3c931faf5494ffc9971b5eaecb54a1a.png
[http_acm.hdu.edu.cn_showproblem.php_pid_1042]: http://acm.hdu.edu.cn/showproblem.php?pid=1042
[http_www.cnblogs.com_phinecos_archive_2009_10_06_1578411.html]: http://www.cnblogs.com/phinecos/archive/2009/10/06/1578411.html