@[Rat_Man](/user/640129) 不妨试试万进制高精度,就是满10000进1,这样可以在不超出int的情况下最大加速计算
by goxjanskloon @ 2022-08-24 13:07:31
只不过是输出会麻烦一点,要补0。
这里给+ - * /的代码:
```cpp
#include<bits/stdc++.h>
using namespace std;
class bignum
{
public:
bignum(string s){this->set(s);}
bignum(long long a){this->set(a);}
bignum(){this->reset();}
void reset();
void set(string s);
void set(long long a);
void print();
int num[10001],len;
char _nm;
};
void bignum::reset()
{
memset(this->num,0,sizeof(this->num));
this->len=1;
this->_nm='+';
}
void bignum::set(string s)
{
this->reset();
if(s[0]=='-')
{
this->_nm='-';
s.erase(0,1);
}
short t=1;
for(int i=s.size()-1;i>=0;i--)
{
this->num[this->len]+=(s[i]-'0')*t;
t*=10;
if(t==10000)
{
t=1;
this->len++;
}
}
while(this->num[this->len]==0&&this->len>1) this->len--;
}
void bignum::set(long long a)
{
this->reset();
if(a<0)
{
this->_nm='-';
a=(+a);
}
while(a>=10000)
{
this->num[this->len++]=a%10000;
a/=10000;
}
this->num[this->len]=a;
}
void bignum::print()
{
if(this->_nm=='-') printf("-");
printf("%d",this->num[this->len]);
for(int i=this->len-1;i>=1;i--)
{
if(this->num[i]>=100&&this->num[i]<1000) printf("0");
else if(this->num[i]>=10&&this->num[i]<100) printf("00");
else if(this->num[i]<1000) printf("000");
printf("%d",this->num[i]);
}
}
short bgnmcmp(bignum a,bignum b)
{
if(a._nm=='+'&&b._nm=='-') return 1;
if(a._nm=='-'&&b._nm=='+') return -1;
if(a.len>b.len) return 1;
if(a.len<b.len) return -1;
for(int i=a.len;i>=1;i--)
{
if(a.num[i]>b.num[i]) return 1;
if(a.num[i]<b.num[i]) return -1;
}
return 0;
}
void bgnmadd(bignum a,bignum b,bignum &s)
{
s.reset();
s.len=(a.len>b.len?a.len:b.len)+1;
for(int i=1;i<=s.len;i++)
{
s.num[i]=a.num[i]+b.num[i];
if(s.num[i]>=10000)
{
s.num[i]-=10000;
s.num[i+1]++;
}
}
if(s.num[s.len]==0) s.len--;
}
void bgnmsub(bignum a,bignum b,bignum &s)
{
s.reset();
s.len=a.len>b.len?a.len:b.len;
if(bgnmcmp(a,b)==1)
for(int i=1;i<=s.len;i++) s.num[i]=a.num[i]-b.num[i];
else if(bgnmcmp(a,b)==-1)
{
s._nm='-';
for(int i=1;i<=s.len;i++) s.num[i]=b.num[i]-a.num[i];
}
else return;
for(int i=1;i<=s.len;i++)
if(s.num[i]<0)
{
s.num[i]+=10000;
s.num[i+1]--;
}
while(s.num[s.len]==0&&s.len>1) s.len--;
}
void bgnmmul(bignum a,bignum b,bignum &s)
{
s.reset();
s.len=a.len+b.len;
for(int i=1;i<=a.len;i++)
for(int j=1;j<=b.len;j++)
{
s.num[i+j-1]+=a.num[i]*b.num[j];
for(int k=i+j-1;s.num[k]>=10000;k++)
{
s.num[k]-=10000;
s.num[k+1]++;
}
}
while(s.num[s.len]==0&&s.len>1) s.len--;
}
void bgnmdiv(bignum a,bignum b,bignum &s,bignum &r)
{
s.reset();
r.reset();
for(int i=a.len;i>=1;i--)
{
bignum v(10000);
bgnmmul(r,v,r);
v.set(a.num[i]);
bgnmadd(r,v,r);
int c=0;
while(bgnmcmp(r,b)>-1)
{
bgnmsub(r,b,r);
c++;
}
s.len++;
s.num[i]=c;
}
while(s.num[s.len]==0&&s.len>1) s.len--;
}
```
by goxjanskloon @ 2022-08-24 13:15:34
希望对你有帮助
by goxjanskloon @ 2022-08-24 13:16:24