首页 > 代码库 > POJ 1503 大整数
POJ 1503 大整数
之前做的大整数,都是一位一位操作。
优化方案:压缩方案。
模板: + - * 操作符重载
#include<cstdio>#include<iostream>#include<cmath>#include<algorithm>#include<cstring>#include<string>#include<vector>using namespace std;struct bigint{ // only positive number; static const int BASE=100000000; static const int WIDTH=8; vector<int> s; //value bigint(long long num=0){ *this = num;} bigint operator = (long long num){ s.clear(); do{ s.push_back(num%BASE); num/=BASE; }while(num>0); return *this; } bigint operator = (const string& str){ s.clear() ; int x,len = (str.length()-1)/WIDTH + 1; for(int i=0;i<len;i++){ int end = str.length() - i*WIDTH; int start = max(0,end - WIDTH); sscanf(str.substr(start,end-start).c_str(),"%d",&x); s.push_back(x); } return *this; } //input&output friend ostream& operator << (ostream &out, const bigint& x){ out << x.s.back(); for(int i=x.s.size()-2;i>=0;i--){ char buf[20]; sprintf(buf,"%08d",x.s[i]); for(int j=0;j<strlen(buf);j++) out << buf[j]; } return out; } friend istream& operator >>(istream &in, bigint& x){ string s; if(!(in>>s)) return in; x=s; return in; } //compare bool operator < (const bigint& b) const { if(s.size()!=b.s.size()) return s.size() < b.s.size(); for(int i=s.size()-1;i>=0;i++) if(s[i]!=b.s[i]) return s[i] < b.s[i]; return false;//equal } bool operator > (const bigint& b) const {return b < *this;} bool operator <= (const bigint& b) const {return !(b < *this);} bool operator >= (const bigint& b) const {return !(*this < b);} bool operator != (const bigint& b) const {return b < *this || *this < b;} bool operator == (const bigint& b) const {return !(b < *this) && !(*this < b);} //calculate bigint operator +(const bigint& b) const { bigint c; c.s.clear(); for(int i=0,g=0;;i++){ if(g==0 && i>=s.size() && i>=b.s.size()) break; int x=g; if(i<s.size()) x+=s[i]; if(i<b.s.size()) x+=b.s[i]; c.s.push_back(x%BASE); g = x/BASE; } return c; } bigint operator +=(const bigint& b){ *this = *this + b; return *this; } bigint operator -(const bigint& b) const { bigint c; c.s.clear(); for(int i=0,g=0;;i++){ if(g==0 && i>=s.size() && i>=b.s.size()) break; int x=g; if(i<s.size()) x+=s[i]; if(i<b.s.size()) x-=b.s[i]; x+=BASE; c.s.push_back(x%BASE); g = x/BASE - 1; } return c; } bigint operator * (const bigint& b) const { bigint c; c.s.clear(); bigint g=0; for(int i=0;;i++){ if(g.s.size()==0 && i>=s.size()+b.s.size()-1) break; bigint x; x.s.clear() ; for(int j=0;j<g.s.size();j++) x.s.push_back(g.s[j]); if(i<s.size()+b.s.size()-1){ for(int j = max(0 , i-(int)s.size()+1);j<=min(i,(int)b.s.size()-1);j++){ bigint t = (long long)b.s[j]*s[i-j]; x += t; } } c.s.push_back(x.s[0]); g.s.clear(); if(x.s.size()>1) for(int j=1;j<x.s.size();j++) g.s.push_back(x.s[j]); } return c; }};int main(){ //freopen("in.txt","r",stdin); bigint a; bigint b = 0; bigint sum = 0; while(cin>>a) { if(a==0) break; sum +=a; } cout<< sum <<endl; return 0;}
POJ 1503 大整数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。