高精度模板
高精度封装大礼包
struct bign{
int d[50], len;
void clean() { while(len > 1 && !d[len-1]) len--; }
bign() { memset(d, 0, sizeof(d)); len = 1; }
bign(int num) { *this = num; }
bign(char* num) { *this = num; }
bign operator = (const char* num){
memset(d, 0, sizeof(d)); len = strlen(num);
for(int i = 0; i < len; i++) d[i] = num[len-1-i] - '0';
clean();
return *this;
}
bign operator = (int num){
char s[20]; sprintf(s, "%d", num);
*this = s;
return *this;
}
bign operator + (const bign& b){
bign c = *this; int i;
for (i = 0; i < b.len; i++){
c.d[i] += b.d[i];
if (c.d[i] > 9) c.d[i]%=10, c.d[i+1]++;
}
while (c.d[i] > 9) c.d[i++]%=10, c.d[i]++;
c.len = max(len, b.len);
if (c.d[i] && c.len <= i) c.len = i+1;
return c;
}
bign operator - (const bign& b){
bign c = *this; int i;
for (i = 0; i < b.len; i++){
c.d[i] -= b.d[i];
if (c.d[i] < 0) c.d[i]+=10, c.d[i+1]--;
}
while (c.d[i] < 0) c.d[i++]+=10, c.d[i]--;
c.clean();
return c;
}
bign operator * (const bign& b)const{
int i, j; bign c; c.len = len + b.len;
for(j = 0; j < b.len; j++) for(i = 0; i < len; i++)
c.d[i+j] += d[i] * b.d[j];
for(i = 0; i < c.len-1; i++)
c.d[i+1] += c.d[i]/10, c.d[i] %= 10;
c.clean();
return c;
}
bign operator / (const bign& b){
int i, j;
bign c = *this, a = 0;
for (i = len - 1; i >= 0; i--)
{
a = a*10 + d[i];
for (j = 0; j < 10; j++) if (a < b*(j+1)) break;
c.d[i] = j;
a = a - b*j;
}
c.clean();
return c;
}
bign operator % (const bign& b){
int i, j;
bign a = 0;
for (i = len - 1; i >= 0; i--)
{
a = a*10 + d[i];
for (j = 0; j < 10; j++) if (a < b*(j+1)) break;
a = a - b*j;
}
return a;
}
bign operator += (const bign& b){
*this = *this + b;
return *this;
}
bool operator <(const bign& b) const{
if(len != b.len) return len < b.len;
for(int i = len-1; i >= 0; i--)
if(d[i] != b.d[i]) return d[i] < b.d[i];
return false;
}
bool operator >(const bign& b) const{return b < *this;}
bool operator<=(const bign& b) const{return !(b < *this);}
bool operator>=(const bign& b) const{return !(*this < b);}
bool operator!=(const bign& b) const{return b < *this || *this < b;}
bool operator==(const bign& b) const{return !(b < *this) && !(b > *this);}
string str() const{
char s[maxn]={};
for(int i = 0; i < len; i++) s[len-1-i] = d[i]+'0';
return s;
}
};
istream& operator >> (istream& in, bign& x)
{
string s;
in >> s;
x = s.c_str();
return in;
}
ostream& operator << (ostream& out, const bign& x)
{
out << x.str();
return out;
}加
string add(string a,string b){
if(a.size() > b.size()) swap(a,b);
b.insert(b.begin(),'0');
int t = 0;
for(int i = b.size()-1,j = a.size()-1;i>=0;i--,j--){
int cur;
if(j>=0) cur = (a[j]-'0') + (b[i]-'0') + t;
else cur = (b[i] - '0') +t;
b[i] = (cur%10) + '0';
t = cur/10;
}
int idx = b.find_first_not_of('0');
return idx != -1? b.substr(idx): "0";
}减
string sub(string a,string b){
//a大b小
int t = 0;
for(int i = a.size()-1,j = b.size()-1;i>=0;i--,j--){
int up = 0,down = 0;
up = (a[i]-'0') + t; t = 0;
if(j>=0) down = (b[j]-'0');
if(up < down) up+=10,t = -1;
int cur = up-down;
a[i] = cur+'0';
}
int idx = a.find_first_not_of('0');
return idx != -1? a.substr(idx) : "0";
}乘（高精度*低精度）
string mul(string a,ll b){
string c = "";
ll t = 0;
for(int i = a.size()-1;i>=0 || t;i--){
if(i>=0) t += (a[i]-'0')*b;
c += (t%10) +'0';
t/=10;
}
reverse(c.begin(),c.end());
return c;
}除（高精度/低精度）
返回商的整数部分
string div(string a,ll b){
string c = "";
ll cur = 0;
for(int i = 0;i<a.size();i++){
cur = cur*10 + (a[i]-'0');
c += to_string(cur/b);
cur %= b;
}
int idx = c.find_first_not_of('0');
return idx!=-1 ? c.substr(idx) : "0";
}比较大小
bool cmp(string a,string b){
int idx1 = a.find_first_not_of('0'),idx2 = b.find_first_not_of('0');
a = idx1!=-1? a.substr(idx1) : "0";
b = idx2!=-1? b.substr(idx2) : "0";
if(a.size() != b.size()) return a.size() >= b.size();
return a>=b;
}所有
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define PI acos(-1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll maxn = 1e6+10;
double eps = 1e-8;
bool cmp(string a,string b){
int idx1 = a.find_first_not_of('0'),idx2 = b.find_first_not_of('0');
a = idx1!=-1? a.substr(idx1) : "0";
b = idx2!=-1? b.substr(idx2) : "0";
if(a.size() != b.size()) return a.size() >= b.size();
return a>=b;
}
string add(string a,string b){
if(a.size() > b.size()) swap(a,b);
b.insert(b.begin(),'0');
int t = 0;
for(int i = b.size()-1,j = a.size()-1;i>=0;i--,j--){
int cur;
if(j>=0) cur = (a[j]-'0') + (b[i]-'0') + t;
else cur = (b[i] - '0') +t;
b[i] = (cur%10) + '0';
t = cur/10;
}
int idx = b.find_first_not_of('0');
return idx != -1? b.substr(idx): "0";
}
string sub(string a,string b){
//a大b小
int t = 0;
for(int i = a.size()-1,j = b.size()-1;i>=0;i--,j--){
int up = 0,down = 0;
up = (a[i]-'0') + t; t = 0;
if(j>=0) down = (b[j]-'0');
if(up < down) up+=10,t = -1;
int cur = up-down;
a[i] = cur+'0';
}
int idx = a.find_first_not_of('0');
return idx != -1? a.substr(idx) : "0";
}
string mul(string a,ll b){
string c = "";
ll t = 0;
for(int i = a.size()-1;i>=0 || t;i--){
if(i>=0) t += (a[i]-'0')*b;
c += (t%10) +'0';
t/=10;
}
reverse(c.begin(),c.end());
return c;
}
string divbb(string a,string b,int len){
//未验证
string c = "";int tag = 1;
for(int i = 1;i<=len;i++){
int cnt = 0;
while(cmp(a,b)){
cnt++;
a = sub(a,b);
}
c += to_string(cnt);
if(tag) c+='.';tag = 0;
a += '0';
}
return c;
}
string div(string a,ll b){
string c = "";
ll cur = 0;
for(int i = 0;i<a.size();i++){
cur = cur*10 + (a[i]-'0');
c += to_string(cur/b);
cur %= b;
}
int idx = c.find_first_not_of('0');
return idx!=-1 ? c.substr(idx) : "0";
}
int main(){
string a;ll b;
cin>>a>>b;
cout<<mul(a,b)<<endl;
return 0;
}
