【干货】高精度模板【加,减,乘,快速幂】

2019-04-14 17:26发布

class="markdown_views prism-dracula"> #include using namespace std; #define N 1010 #define LL long long #define fu(a,b,c) for(int a=b;a<=c;++a) #define fd(a,b,c) for(int a=b;a>=c;--a) const int Base=10000; struct Big{ int len,w,t[N]; Big(){len=w=1;memset(t,0,sizeof(t));} }ans; Big change(int a){ Big c;c.len=0; if(a<0)c.w=-1; a=abs(a); while(a)c.t[++c.len]=a%Base,a/=Base; return c; } void print(Big c){ if(c.w==-1)printf("-"); printf("%d",c.t[c.len]); fd(i,c.len-1,1)printf("%04d",c.t[i]); printf(" "); } bool unsigned_cmp(Big a,Big b){//只比较数字大小 if(a.len>b.len)return 1; if(a.len<b.len)return 0; fd(i,a.len,1){ if(a.t[i]>b.t[i])return 1; if(a.t[i]<b.t[i])return 0; } return 1; } Big unsigned_add(Big a,Big b){ Big c;c.len=max(a.len,b.len); fu(i,1,c.len)c.t[i]=a.t[i]+b.t[i]; fu(i,1,c.len){ if(c.t[i]>Base){ c.t[i]-=Base; c.t[i+1]++; if(i==c.len)c.len++; } } return c; } Big unsigned_sub(Big a,Big b){ Big c;c.len=max(a.len,b.len); fu(i,1,c.len)c.t[i]=a.t[i]-b.t[i]; fu(i,1,c.len){ if(c.t[i]<0){ c.t[i]+=Base; c.t[i+1]--; } } fd(i,c.len,1){ if(!c.t[i])c.len--; else break; } return c; } Big add(Big a,Big b){ Big c; if(unsigned_cmp(b,a))swap(a,b); if(a.w==1&&b.w==1)c=unsigned_add(a,b),c.w=1; if(a.w==1&&b.w==-1)c=unsigned_sub(a,b),c.w=1; if(a.w==-1&&b.w==1)c=unsigned_sub(a,b),c.w=-1; if(a.w==-1&&b.w==-1)c=unsigned_add(a,b),c.w=-1; return c; } Big sub(Big a,Big b){b.w=0-b.w;return add(a,b);} Big mul(Big a,Big b){ Big c;c.w=a.w*b.w; c.len=a.len+b.len-1; fu(i,1,a.len) fu(j,1,b.len) c.t[i+j-1]+=a.t[i]*b.t[j]; fu(i,1,c.len){ if(c.t[i]>Base){ c.t[i+1]+=c.t[i]/Base; c.t[i]%=Base; if(i==c.len)c.len++; } } return c; } Big fast_pow(Big a,int b){ Big ans;ans.t[1]=1; if((b&1)&&a.w==-1)ans.w=-1; while(b){ if(b&1)ans=mul(ans,a); b>>=1; a=mul(a,a); } return ans; } int main(){ return 0; }