高精度

高精度

因为c++没有大数类，最大的类型是 UNSIGNED LONG LONG 数值范围只有 \([0,2^{64}-1]\)，没法满足需要，int128似乎不是正统语言中的内容，略。

所以高精度就是解决大数运算的技巧，把数组按位存储，一般从低位到高位。进制无所谓，但是常用10，为了节约复杂度有时会使用压位，即设 \(10^k\) 进制，可以在复杂度优化一个 \((压的位数)\)，但是会遇到运算溢出的问题。，一般使用结构体，让代码更简洁。还要重载运算符，也是避免大量函数影响代码美观。

接下来讨论运算：

\(n,m\) 为两个高精数字位数，n为运算符左边的数，m为运算符右边的数

\(p\) 为低精数字，在运算符右边

加: \(O(n+m)\)

减：\(O(n+m)\)

朴素乘: \(O(nm)\) NTT乘：\(O((n+m)\log(n+m))\)

低精乘: \(O(n)\)

低精除：\(O(n)\)

低精取模：\(O(n)\)

以下是基本模板

const int MAXL=2000;
struct Number{
    long long a[MAXL+10];
    Number(){memset(a,0,sizeof a);}
    Number(int x){
        for(int i=1;i<=MAXL;++i){
            a[i] = x%10;
            x /= 10;
        }
    }
    Number operator + (const Number B)const{
        Number C;
        for(int i=1;i<=MAXL;++i){
            C.a[i] += a[i]+B.a[i];
            if(C.a[i]>=10){
                C.a[i+1] += C.a[i]/10;
                C.a[i] %= 10;
            }
        }
        return C;
    }
    Number operator * (const long long x)const{
        Number C;
        for(int i=1;i<=MAXL;++i){
            C.a[i] += a[i]*x;
            if(C.a[i]>=10){
                C.a[i+1] += C.a[i]/10;
                C.a[i] %= 10;
            }
        }
        return C;
    }
    Number operator / (const long long x)const{
        Number C;
       	long long tmp=0;
        for(int i=MAXL;i>=0;--i){
            C.a[i] = (tmp*10+a[i])/x;
            tmp = (tmp*10+a[i])%x;
        }
        return C;
    }
    void print(){
        int i=MAXL;
        while(i>=1&&a[i]==0)--i;//要判边界
        if(i<1)putchar('0');
        for(;i>=1;--i){
			printf("%c",'0'+a[i]);
		}
        putchar('\n');
    }
};

vector + NTT 版本

const int Base=10;
typedef long long ll;
int r[1<<19];
int G=3,Gi=332748118;
void ntt(vector<ll> &a,int s,int INTT){
	for(int i=0;i<s;++i)
		if(i<r[i])
			swap(a[i],a[r[i]]);
	for(int len=2;len<=s;len<<=1){
		ll gn=qpow(INTT==-1?Gi:G,(mod-1)/len,mod);
		int k=len/2;
		for(int i=0;i<s;i+=len){
			ll g=1;
			for(int j=0;j<k;++j,g=g*gn%mod){
				ll tmp=a[i+j+k]*g%mod;
				a[i+j+k]=(a[i+j]-tmp+mod)%mod;
				a[i+j]=(a[i+j]+tmp)%mod;
			}
		}
	}
	if(INTT==-1){
		ll inv=qpow(s,mod-2,mod);
		for(int i=0;i<s;++i)a[i]=a[i]*inv%mod;
	}
}
struct Number{
	vector<ll> a;
	Number(){
		a.clear();
	}
	Number(int n){
		while(n){
			a.emplace_back(n%Base);
			n/=Base;
		}
	}
	void read(){
		string s;
		cin>>s;
		reverse(s.begin(),s.end());
		for(int i=0;i<(int)s.size();i+=1){
			int t=0;
			for(int j=min((int)s.size(),i+1)-1;j>=i;--j)t=t*10+s[j]-'0';
			a.emplace_back(t);
		}
	}
	Number operator + (int b){
		Number C;
		C.a=a;
		C.a[0]+=b;
		for(int i=0;i<(int)a.size();++i){
			if(C.a[i]>=Base){
				if(i+1<(int)a.size())C.a[i+1]+=C.a[i]/Base;
				else C.a.emplace_back(C.a[i]/Base);
				C.a[i]%=Base;
			}else break;
		}
		return C;
	}
	Number operator * (Number b){
		int n=a.size()-1+b.a.size()-1+1;
		int s=1;
		while(s<n)s<<=1;
		for(int i=0;i<s;++i)
			r[i]=(r[i>>1]>>1)|((i&1)*(s>>1));
		vector<ll> A=a,B=b.a;
		A.resize(s);
		B.resize(s);
		ntt(A,s,1);
		ntt(B,s,1);
		for(int i=0;i<s;++i)A[i]=A[i]*B[i]%mod;
		ntt(A,s,-1);
		Number C;
		C.a=A;
		for(int i=0;i<C.a.size()-1;++i){
			if(C.a[i]>=Base){
				C.a[i+1]+=C.a[i]/Base;
				C.a[i]%=Base;
			}
		}
		while(C.a.back()==0)C.a.pop_back();
		return C;
	}
	Number operator / (int b){
		Number C;
		C.a.resize(a.size(),0);
		ll t=0;
		for(int i=a.size()-1;i>=0;--i){
			t=t*Base+a[i];
			C.a[i]=t/b;
			t%=b;
		}
		while(C.a.back()==0)C.a.pop_back();
		return C;
	}
	void print(){
		if(a.size()==0){
			puts("0");
			return;
		}
		printf("%lld",a.back());
		for(int i=a.size()-2;i>=0;--i)printf("%lld",a[i]);
		puts("");
	}
};