高精模板

2019-04-13 22:09发布

站内文章 / 模拟电子
16882 0 921
class="markdown_views prism-atom-one-light"> #include using namespace std; typedef long long ll; const int N=10002,M=1e9; struct NUM{ bool fl;int t; ll a[N/9]; friend void print(NUM x){ if (!x.t){puts("0");return;} if (!x.fl) putchar('-'); printf("%lld",x.a[--x.t]); int t[9]; for (int i=x.t-1;i>=0;i--){ memset(t,0,sizeof(t)); for (int j=0;j<9;j++) t[j]=x.a[i]%10,x.a[i]/=10; for (int j=8;j>=0;j--) putchar(t[j]|48); } puts(""); } friend bool operator>(NUM x,NUM y){//abs值比较 if (x.t!=y.t) return x.t>y.t; for (int i=x.t-1;i>=0;i--) if (x.a[i]!=y.a[i]) return x.a[i]>y.a[i]; return 0; } friend NUM operator+(NUM x,NUM y){//高精加 if (x.fl==y.fl){ int i; for (i=0;iif (i+1>=x.t) x.a[i+1]=0; if (iif (x.a[i]>=M) x.a[i+1]++,x.a[i]-=M; } x.t=i; }else{ if (y>x) swap(x,y); for (int i=0;iif (x.a[i]<0) x.a[i]+=M,x.a[i+1]--; } while (x.t && !x.a[x.t-1]) x.t--; } return x; } friend NUM operator-(NUM x,NUM y){y.fl^=1;return x+y;} friend NUM operator*(NUM x,NUM y){//高精乘 NUM z;z.t=x.t+y.t; memset(z.a,0,z.t<<3); z.fl=x.fl==y.fl; for (int i=0;ifor (int j=0;j1]+=z.a[i+j]/M; z.a[i+j]%=M; } if (z.t && !z.a[z.t-1]) z.t--; return z; } friend NUM operator*(NUM x,int y){//单精乘 int i; for (i=0;ifor (i=0;iif (i+1>=x.t) x.a[i+1]=0; x.a[i+1]+=x.a[i]/M,x.a[i]%=M; } x.t=i; return x; } friend NUM operator/(NUM x,int y){//单精除 ll k=0; for (int i=x.t-1;i>=0;i--){ k=k*M+x.a[i]; x.a[i]=k/y; k%=y; } while (x.t && !x.a[x.t-1]) x.t--; return x; } friend NUM div(NUM x,NUM y,bool fl){//高精除 NUM z;z.fl=x.fl==y.fl;z.t=x.t-y.t+1; if (z.t<=0){ z.t=0; return fl?z:x; } memset(z.a,0,z.t<<3); x.fl=y.fl=1; for (int i=z.t-1;i>=0;i--){ for (int j=1<<29;j;j>>=1){ NUM tmp=y*j;bool fl=tmp.t+i<=x.t; if (!fl) continue; if (tmp.t+i==x.t){ for (int k=tmp.t-1;k>=0;k--) if (x.a[k+i]!=tmp.a[k]){ fl=tmp.a[k]break; } if (!fl) continue; } z.a[i]|=j; for (int k=0;kif (x.a[k+i]<0) x.a[k+i+1]--,x.a[k+i]+=M; } while (x.t && !x.a[x.t-1]) x.t--; } } while (z.t && !z.a[z.t-1]) z.t--; return fl?z:x; } friend NUM operator/(NUM x,NUM y){return div(x,y,1);} friend NUM operator%(NUM x,NUM y){return div(x,y,0);} friend NUM gcd(NUM x,NUM y){ int cnt=0;NUM T; while (1){ if (!x.t || !y.t){ NUM p,z;p.fl=z.fl=1; p.a[0]=2; p.t=z.t=z.a[0]=1; for (;cnt;cnt>>=1,p=p*p) if (cnt&1) z=z*p; if (x.t) return z*x; else return z*y; } bool f1=0,f2=0; if (!(x.a[0]&1)) x=x/2,f1=1; if (!(y.a[0]&1)) y=y/2,f2=1; if (f1 && f2) cnt++; if (x>y) x=x-y; else T=x,x=y-x,y=T; } } }; NUM toNUM(char s[]){ ll f[10]; f[0]=1; for (int i=1;i<10;i++) f[i]=f[i-1]*10; NUM A; A.t=strlen(s);A.fl=1; memset(A.a,0,(A.t-1)/9+1<<3); for (int i=A.t-1;i>=0;i--) A.a[(A.t-1-i)/9]+=f[(A.t-1-i)%9]*(s[i]^48); A.t=(A.t-1)/9+1; return A; }

热门文章