绪言
自从有了高精度模板，妈妈再也不用怕我不会打高精度了！
代码
代码长度与日俱增啊~~~
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std; bool insigma(char ch){
return ch=='-'||(''<=ch&&ch<='');
} const int maxn = ;
struct number{
int num[maxn];
int len;
bool fu; number(){//初始化
len=fu=;
memset(num,,sizeof(num));
} int updata_len(){//更新长度
for(int i=maxn-;i>=;i--) if(num[i]) return len=i+;
return len=;
} // /*
number operator= (int x){//隐式转换
fu=(x<);
num[]=abs(x);
if(x>) carry_bit();
if(x<-) back_space();
return *this;
}
// */
/*
number (int x){//有bug的构造函数 暂时用重载=替代
fu=(x<0);
num[0]=abs(x);
if(x>9) carry_bit();
if(x<-9) back_space();
}
*/ void input(){
// /*
string a;
cin>>a;
if(a[]=='-'){
fu=;
len=a.size()-;
for(unsigned int i=;i<a.size()-;i++) num[i]=a[a.size()-i-]-'';
}
else{
len=a.size();
for(unsigned int i=;i<a.size();i++) num[i]=a[a.size()-i-]-'';
} // */
/*
len=0;
char ch;
while(!insigma(ch=getchar()));
if(ch=='-')
fu=true;
else
num[len++]=ch-'0';
while(isdigit(ch=getchar())){
num[len++]=ch-'0';
}
int t;
for(int i=0;i<len;i++)
{
t=num[i];
num[i]=num[len-i-1];
num[len-i-1]=t;
}
*/
} void output(){
if(fu) cout<<"-";
bool flag=;
for(int i=len;i>;i--){
if(num[i]) flag=;
if(num[i]>) carry_bit();
if(flag) putchar(num[i]+'');//putchar加速
}
putchar(num[]+'');
} friend istream & operator>> (istream &in, number &obj);
friend ostream & operator<< (ostream &out, number &obj); int compare(number x){//2= 1> 0<
if(fu^x.fu){
if(fu) return ;
else return ;
}
for(int i=max(len,x.len);i>=;i--)
{
if(num[i]>x.num[i]) return !fu;//大于 (1)
if(num[i]<x.num[i]) return fu;//小于 (0)
}
return ;//相等
} //利用compare()重载比较运算符 bool operator> (number x){
return (compare(x)==);
} bool operator< (number x){
return (compare(x)==);
} bool operator>= (number x){
return !(*this<x);
} bool operator<= (number x){
return !(*this>x);
} bool operator== (number x){
return compare(x)==;
} bool operator!= (number x){
return compare(x)!=;
} number operator++ (){
num[]++;
if(num[]>) carry_bit();
return *this;
} number operator++ (int){
number save=*this;
++*this;
return save;
} number operator-- (){
num[]--;
if(num[]<) back_space();
return *this;
} number operator-- (int){
number save=*this;
num[]--;
if(num[]<) back_space();
return save;
} bool judge_zero(){
for(int i=maxn-;i>=;i--)
if(num[i]) return ;
return ;
} bool judge_non_zero(){
return !judge_zero();
} bool convert_bool(){
return !judge_zero();
} bool even(){
if(num[]%) return ;
return ;
} bool odd(){
if(num[]%) return ;
return ;
} void carry_bit(){
for(int i=;i<maxn;i++){
num[i+]+=num[i]/;
num[i]%=;
}
updata_len();
} void back_space(){
for(int i=;i<maxn;i++){
while(num[i]<) num[i]+=,num[i+]--;
}
} number operator+ (int x){
number newness=*this;
newness.num[]+=x;
if(newness.num[]>) newness.carry_bit();
return newness;
} number operator+ (number x){
number res=x;
for(int i=;i<maxn;i++)
{
res.num[i]+=num[i];
}
res.carry_bit();
return res;
} number operator+= (int x){
*this=(*this+x);
return *this;
} number operator+= (number x){
*this=*this+x;
return *this;
} number operator- (number x){
number i,j;
if(compare(x)) {i=*this,j=x;}
else {i=x,j=*this;}
for(int t=;t<maxn;t++)
{
i.num[t]-=j.num[t];
}
i.back_space();
return i;
} number operator-= (number x){
*this=*this-x;
return *this;
} number operator* (number x){
number sum;
sum.fu=fu^x.fu;
for(int i=;i<updata_len();i++)
for(int j=;j<x.updata_len();j++)
{
if(i+j>maxn-) continue;
sum.num[i+j]+=num[i]*x.num[j];
}
sum.carry_bit();
return sum;
} number operator*= (number x){
return *this=*this*x;
} number factor(){
number ans,t;
t.num[]=;
ans.num[]=;
for(;t<=*this;t.num[]+=,t.carry_bit())
ans*=t;
return ans;
} number division2(){
for(int i=maxn-;i>=;i--){
if(num[i]&&&i!=) num[i-]+=;
num[i]>>=;
}
return *this;
}
}; istream & operator>> (istream &in, number &obj)
{
string a;
in>>a;
if(a[]=='-'){
obj.fu=;
obj.len=a.size()-;
for(unsigned int i=;i<a.size()-;i++) obj.num[i]=a[a.size()-i-]-'';
}
else{
obj.len=a.size();
for(unsigned int i=;i<a.size();i++) obj.num[i]=a[a.size()-i-]-'';
}
if (!in) obj = number();
return in;
} ostream & operator<< (ostream &out, number &obj)
{
if(obj.fu) cout<<"-";
bool flag=;
for(int i=obj.len;i>;i--){
if(obj.num[i]) flag=;
if(obj.num[i]>) obj.carry_bit();
if(flag) out<<obj.num[i];
}
out<<obj.num[];
return out;
} number gcd_rec(number a,number b){
if(b.judge_zero()) return a;
return gcd_rec(b,a-b);
} number gcd(number a,number b){
if(a.judge_zero()) return a;
number t;
for(;;t=b,b=a-b,a=t)
if(b.judge_zero()) return a;
return a;
} number power(number a,number n){
number zero;
number c;c=;
for(;n>zero;n.division2(),a*=a) if(n.odd()) c*=a;
return c;
} int main()
{
freopen("gcd.in","r",stdin);
freopen("gcd.out","w",stdout);
number a,b,c;
cin>>a>>b;
c=gcd(a,b);
cout<<c;
return ;
}
折柳的高精度模板Code
更新日志
其实我是在写了300行以后才来写这篇博客的，所以之前的时间点就不计了吧！
（2019-11-05ago）
加法
进位
构造
比较
减法
退位
递归求gcd
非递归gcd
乘法
阶乘
iostream
除以2
判断奇偶
快速幂
……
细节实现
相信这里有许多我（以前）不会的c++语言用法吧。我把它们都记录下来了呢！
构造函数
当我们定义一个number时，由于可能是局部变量，我们就要先将其赋初值
但是number不是int，不是double，要是我们要赋初值的话，还得将其所有的变量（even arraies！）赋初值！
所以我为了在使用number时方便，在网上找了个东西叫做 构造函数
函数与结构体（或类，一下省略）同名，没有返回值（不是void！）
在新定义一个number时会自动调用
作用大概就是 赋初值 吧
（PS：还有个函数叫 析构函数，用于释放结构体内存时操作（例如：删除指针等），有兴趣可以去看看）
number(){
len=fu=;
memset(num,,sizeof(num));
}
但要是我们要给一个number赋初值怎么办？
一个即将退役的老OIer告诉我，再来一个构造函数，但是它是要传参的呗！
但是，由于我不会用，只好重载的=（赋值运算符）来赋初值。
number operator= (int x){//隐式转换（？）
fu=(x<);
num[]=abs(x);
if(x>) carry_bit();
if(x<-) back_space();
return *this;
}
也许以后我就会用了吧！
重载前缀自增自减运算符
本来我想到了自增自减有前缀和后缀之分，但是不知道该怎么打……
所以就先打了个不知道是哪种的operator+
number operator++ (){
num[]++;
if(num[]>) carry_bit();
return *this;
}
结果发现只有前缀才能用。
那么后缀的该怎么打呢？
重载后缀自增自减运算符
几番查找后，终于在《C++ Primer Plus》里面找到了
只要在（）里加一个int即可
（原理不知）
number operator++ (int){
number save=*this;
++*this;
return save;
}
这里我甚至还偷懒地在后缀里用了前缀……本来就没错嘛！
重载赋值运算符(int转num高精度)
见 构造函数 末尾部分
number operator= (int x){//隐式转换
fu=(x<);
num[]=abs(x);
if(x>) carry_bit();
if(x<-) back_space();
return *this;
}
重载输入输出流运算符(友元)
首先我为了输入输出各自写了一个成员函数
void input(){
string a;
cin>>a;
if(a[]=='-'){
fu=;
len=a.size()-;
for(unsigned int i=;i<a.size()-;i++) num[i]=a[a.size()-i-]-'';
}
else{
len=a.size();
for(unsigned int i=;i<a.size();i++) num[i]=a[a.size()-i-]-'';
}
}
void output(){
if(fu) cout<<"-";
bool flag=;
for(int i=len;i>;i--){
if(num[i]) flag=;
if(num[i]>) carry_bit();
if(flag) putchar(num[i]+'');//putchar加速
}
putchar(num[]+'');
}
后来，我想：看看人家STL-string，都可以直接拿cin cout输入输出了，你怎么就不可以做到呢？
我又去网上，书中找了找怎么重载流运算符……
不想讲了，就是套模板，把之前写的那个input和output套进去就可以了嘛！
But，由于stream是一个已经封装好了的类，你也不能修改头文件中的内容，怎么办呢？
answer：用友元！它可以“打入敌人内部”进行一些操作！
友元函数声明（要放在结构体中！）
friend istream & operator>> (istream &in, number &obj);
friend ostream & operator<< (ostream &out, number &obj);
即 在正常的函数前加上friend即可
友元函数定义（要放在全局中！）
istream & operator>> (istream &in, number &obj)
{
string a;
in>>a;
if(a[]=='-'){
obj.fu=;
obj.len=a.size()-;
for(unsigned int i=;i<a.size()-;i++) obj.num[i]=a[a.size()-i-]-'';
}
else{
obj.len=a.size();
for(unsigned int i=;i<a.size();i++) obj.num[i]=a[a.size()-i-]-'';
}
if (!in) obj = number();
return in;
} ostream & operator<< (ostream &out, number &obj)
{
if(obj.fu) cout<<"-";
bool flag=;
for(int i=obj.len;i>;i--){
if(obj.num[i]) flag=;
if(obj.num[i]>) obj.carry_bit();
if(flag) out<<obj.num[i];
}
out<<obj.num[];
return out;
}
重载判断符运算符
那么多比较函数，我一下子那写的过来呢？
本来我都是没有operator这些比较运算符的，只用了一个int compare(number)就好了
PS：为什么返回值不是bool而是int呢？因为返回的信息可能不只有大于，小于，还会有等于呀！
int compare(number x){//2= 1> 0<
if(fu^x.fu){
if(fu) return ;
else return ;
}
for(int i=max(len,x.len);i>=;i--)
{
if(num[i]>x.num[i]) return !fu;//大于 (1)
if(num[i]<x.num[i]) return fu;//小于 (0)
}
return ;//相等
}
后来，我觉得这样十分的不直观，而且有时容易错，还是个成员函数，调用时是a.compare(b)这样的形式的……
所以我就把"<",">","<=",">=","==","!="都重载了！
Impression
现在的长度是有限的而且在枚举时也可能会有大量时间浪费
尽管已经引进了len和updata_len()，但是这两个玩意的作用还是较小，用法比较麻烦
希望能像STL的某些容器那样可自动改变大小，已经O(1)就可以知道number的位数
不知道为什么，一个number表达式不可以用cout<<输出？
就像
a,b为number时，cout<<(a+b);不可以；
但是
a,b为int时，cout<<(a+b);可以！
是因为operator<< 里的参数obj为引用吗？
除法（二分）
这个玩意还有存在许多许多可以更新&改进的地方，欢迎提建议！