高精度结构体定义：
struct numlist { static const short L = 85;//做乘法FFT，要开到最大乘数长度的4倍 char a[L]; short len; void ini(string s)//字符串输入 { fill(a, a + L, 0); for (int i = s.length() - 1; i >= 0; i--) a[s.length() - i - 1] = s[i] - '0'; len = s.length(); if(s[0]=='0') len=0; } void ini(long long int num)//数字输入 { fill(a, a + L, 0); len = 0; while (num) { a[len++] = num % 10; num /= 10; } } void updateBit()//更新位数,约定0的位数是0 { len = 0; for (int i = 0; i<L; i++) { if (a[i] != 0) len = i + 1; if (a[i] >= 10) { int temp = a[i] / 10; a[i] %= 10; a[i + 1] += temp; } if (a[i]<0) { int temp = -(a[i] % 10 != 0) + a[i] / 10; a[i] %= 10; if (a[i]<0) a[i] += 10; a[i + 1] += temp; } } } void print()//测试输出 { if (len == 0) { cout << 0 << endl; //puts("0"); return; } for (int i = len - 1; i >= 0; i--) cout << (int)a[i]; cout << endl; /* for(int i=len-1;i>=0;i--) printf("%d",a[i]); printf(" "); */ } };
大小比较
int BitCmp(numlist a,numlist b)//1:a>b,-1:a<b,0:a==b { if(a.len!=b.len) return a.len>b.len?1:-1; for(int i=a.len-1;i>=0;i--) if(a.a[i]!=b.a[i]) return a.a[i]>b.a[i]?1:-1; return 0; }
高精度加减
1、高精度加单精度
numlist Badd(numlist a,long long int num) { long long int p=0; while(num) { a.a[p++]+=num%10; num/=10; } a.updateBit(); return a; }
2、高精度加高精度（后者可以成倍加入前者，也可以变形实现高精度乘单精度）
numlist Badd(numlist a,numlist b,int f) { int mx=a.len; if(b.len>mx) mx=b.len; for(int i=0;i<mx;i++) a.a[i]+=b.a[i]*f; a.updateBit(); return a; }
高精度取余
1、高精度取单精度
int mod(numlist a,int b)//高精度取余单精度 输出余数 { int temp=0; for(int i=a.len-1; i>=0; i--) temp=(temp*10+a.a[i])%b; return temp; }
高精度除法
1、高精度除单精度
numlist div(numlist a,int b) { for(int i=a.len-1;i>=0;i--) { int temp=a.a[i]%b; a.a[i]/=b; if(i!=0) a.a[i-1]+=temp*10; } a.updateBit(); return a; }
高精度乘法
1、高精度乘高精度
numlist Bmut(numlist a,numlist b) { numlist c; c.ini(0); for(int i=0; i<a.len; i++) for(int j=0; j<b.len; j++) c.a[i+j]+=a.a[i]*b.a[j]; c.updateBit(); return c; }
2、高精度乘法FFT优化
struct numlist { static const int L = 55000*4;//做乘法FFT，要开到最大乘数长度的4倍 int a[L]; int len; void ini(string s)//字符串输入 { fill(a, a + L, 0); for (int i = s.length() - 1; i >= 0; i--) a[s.length() - i - 1] = s[i] - '0'; len = s.length(); } void ini(long long int num)//数字输入 { fill(a, a + L, 0); len = 0; if (num == 0) len++; while (num) { a[len++] = num % 10; num /= 10; } } void updateBit()//更新位数,约定0的位数是0 { len = 0; for (int i = 0; i<L; i++) { if (a[i] != 0) len = i + 1; if (a[i] >= 10) { int temp = a[i] / 10; a[i] %= 10; a[i + 1] += temp; } if (a[i]<0) { int temp = -(a[i] % 10 != 0) + a[i] / 10; a[i] %= 10; if (a[i]<0) a[i] += 10; a[i + 1] += temp; } } } void print()//测试输出 { if (len == 0) { cout << 0 << endl; //puts("0"); return; } for (int i = len - 1; i >= 0; i--) cout << a[i]; cout << endl; /* for(int i=len-1;i>=0;i--) printf("%d",a[i]); printf(" "); */ } }; struct Complex // 复数 { double r, i; Complex(double _r = 0, double _i = 0) :r(_r), i(_i) {} Complex operator +(const Complex &b) { return Complex(r + b.r, i + b.i); } Complex operator -(const Complex &b) { return Complex(r - b.r, i - b.i); } Complex operator *(const Complex &b) { return Complex(r*b.r - i*b.i, r*b.i + i*b.r); } }; void change(Complex y[], int len) // 二进制平摊反转置换 O(logn) { int i, j, k; for (i = 1, j = len / 2; i < len - 1; i++) { if (i < j)swap(y[i], y[j]); k = len / 2; while (j >= k) { j -= k; k /= 2; } if (j < k)j += k; } } void fft(Complex y[], int len, int on) //FFT:on=1; IFFT:on=-1 { change(y, len); for (int h = 2; h <= len; h <<= 1) { Complex wn(cos(-on * 2 * PI / h), sin(-on * 2 * PI / h)); for (int j = 0; j < len; j += h) { Complex w(1, 0); for (int k = j; k < j + h / 2; k++) { Complex u = y[k]; Complex t = w*y[k + h / 2]; y[k] = u + t; y[k + h / 2] = u - t; w = w*wn; } } } if (on == -1) for (int i = 0; i < len; i++) y[i].r /= len; } const LL N = 55000 * 4; Complex n1[N], n2[N]; int ans[N]; numlist Bmut(numlist &a, numlist &b) { int len1 = a.len, len2 = b.len; int len = 1; while (len < len1 + len2 + 3)len <<= 1; for (int i = 0; i < len; i++) n1[i] = Complex(0, 0), n2[i] = Complex(0, 0); for (int i = len1 - 1; i >= 0; i--) n1[i] = Complex(a.a[i], 0); for (int i = len2 - 1; i >= 0; i--) n2[i] = Complex(b.a[i], 0); fft(n1, len, 1); fft(n2, len, 1); for (int i = 0; i<len; i++) n2[i] = n2[i] * n1[i]; fft(n2, len, -1); numlist c; c.ini(0); for (int i = 0; i < len; i++) { c.a[i] += (int)(n2[i].r + 0.005); c.a[i + 1] += c.a[i] / 10; c.a[i] %= 10; if (c.a[i] != 0)c.len = i + 1; } //c.updateBit(); return c; }
高精度快速幂
numlist fastMi(numlist a,int b) { numlist mut; mut.ini(1); while(b) { if(b%2!=0) mut=Bmut(mut,a); a=Bmut(a,a); b/=2; } return mut; }
高精度开方
1、模拟手算
numlist Bsqrt(numlist a) { numlist rec,num100,high,preBit; num100.ini(100); string ans="";//顺序记录每一位 int pos=a.len-(!(a.len%2)+1); numlist temp; int initNum=0; for(int i=a.len-1;i>=pos;i--) initNum*=10,initNum+=a.a[i]; ans+=sqrt(initNum)+'0'; preBit.ini(ans); initNum-=(int)sqrt(initNum)*(int)sqrt(initNum); temp.ini(initNum);//部分余数 pos-=2; for(;pos>=0;pos-=2) { ans+='0'; for(int i=preBit.len;i>0;i--) preBit.a[i]=preBit.a[i-1]; preBit.a[0]=0; preBit.len++; high=preBit; high=Add(high,high,1); temp=Bmut(temp,num100); temp=Add(temp,a.a[pos]+a.a[pos+1]*10); numlist pn,pn1; numlist pnow,ppre; int p=5; do { pn.ini(p),pn1.ini(p-1); pnow=Bmut(Add(high,p),pn); ppre=Bmut(Add(high,p-1),pn1); if(BitCmp(temp,ppre)<0) p--; else if(BitCmp(pnow,temp)<=0) p++; else break; }while(1); p--; preBit.a[0]=p; pn.ini(p); pnow=Bmut(Add(high,p),pn); temp=Add(temp,pnow,-1); ans[ans.length()-1]=p+'0'; } rec.ini(ans); return rec; }