大佬们帮我!
查看原帖
大佬们帮我!
1144339
forever_Neuer楼主2024/9/4 21:18

我花费千辛万苦写了个顶呱呱的高精度模板,却因无 FFTFFT 优化不太满足……

然后,自己写了个 700700 多 ms 的代码不太满足……

大佬帮我写一个!

#include "bits/stdc++.h"
using namespace std;
class Big{
	#define Mod 100000000
	#define N 1000007
	#define LL long long
	private:
		int p[N],sz,aux[N];
	public:
		inline void in(void){this->clear();memset(aux, 0, sizeof(aux));int tot=0,x=0,y,k=1;char ch=getchar();int fu=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')fu*=-1;for(;ch>='0'&&ch<='9';ch=getchar()){if(tot==1 && !aux[tot])aux[tot]=ch-'0';else aux[++tot]=ch-'0';}sz=(tot+7)/8,y=(tot-1)%8+1;for(int i=tot;i>=y;i-=8,x=0){for(int j=7;j>=0;j=~-j){if(i<=j) continue;x=(x<<1)+(x<<3)+aux[i-j];}p[k++]=x;}p[sz]*=fu;}
		inline void out(bool u=false){if(!sz) return (void)printf("0");printf("%d",p[sz]);for(int i=sz-1;i;i=~-i) printf("%08d",p[i]);if(u) putchar('\n');}
		
	public:
		inline Big operator=(const int &d){int b=d,fu=1;if(b<0) b*=-1,fu=-1;this->clear();do p[++sz]=b%Mod,b/=Mod;while(b);return p[sz]*=fu,*this;}
		inline Big operator=(const LL &d){LL b=d;int fu=1;if(b<0) b*=-1,fu=-1;this->clear();do p[++sz]=b%Mod,b/=Mod;while(b);return p[sz]*=fu,*this;}
		inline Big operator+(const int &d){LL x=d;int fu=1;Big c;if(p[sz]<0 && x<0) p[sz]*=-1,x*=-1,fu=-1;else if(p[sz]<0) return p[sz]*=-1,(c=x)-*this;else if(x<0) return x*=-1,*this-x;for(register int i=1;i<=sz && x;i=-~i)x=x+p[i],p[i]=x%Mod,x=x/Mod;if(x) p[++sz]=x;return p[sz]*=fu,*this;}
		inline Big operator+(const LL &d){LL x=d;int fu=1;Big c;if(p[sz]<0 && x<0) p[sz]*=-1,x*=-1,fu=-1;else if(p[sz]<0) return p[sz]*=-1,(c=x)-*this;else if(x<0) return x*=-1,*this-x;for(register int i=1;i<=sz && x;i=-~i)x=x+p[i],p[i]=x%Mod,x=x/Mod;if(x) p[++sz]=x;return p[sz]*=fu,*this;}
		inline Big operator+(const Big &d){Big c,a=*this,b=d;int fu=1;if(a.p[a.sz]<0 && b.p[b.sz]<0) a.p[a.sz]*=-1,b.p[b.sz]*=-1,fu=-1;else if(a.p[a.sz]<0)return a.p[a.sz]*=-1,b-a;else if(b.p[b.sz]<0)return b.p[b.sz]*=-1,a-b;if(a<b) a.swap(b);if(b.sz<3)return c=a+b.toLL(),c.p[c.sz]*=fu,c;LL x=0;for(int i=1;i<=a.sz;i=-~i) x=x+a.p[i]+b.p[i],c.p[i]=x%Mod,x=x/Mod;c.sz=a.sz;if(x) c.p[++c.sz]=x;return c.p[c.sz]*=fu,c;}
		inline Big operator-(const Big &d){Big a=*this,c,b=d;int fu=1;if(a.p[a.sz]<0 && b.p[b.sz]<0) a.p[a.sz]*=-1, b.p[b.sz]*=-1,fu*=-1;else if(a.p[a.sz]<0) return a.p[a.sz]*=-1,c=a+b,c.p[c.sz]*=-1,c;else if(b.p[b.sz]<0) return b.p[b.sz]*=-1,a+b;LL x=1,k=0;if(a<b) a.swap(b),fu*=-1;if(a==b) return c=0;for(int i=1; i<=a.sz;i=-~i)x=x+a.p[i]+Mod-1-b.p[i],c.p[i]=x%Mod,x/=Mod;for(c.sz=a.sz; c.p[c.sz]==0;c.sz=~-c.sz);return c.p[c.sz]*=fu,c;}
		inline Big operator-(const int &d){Big c;int b=d;int fu=1;if(p[sz]<0 && b<0) p[sz]*=-1, b*=-1,fu*=-1;else if(p[sz]<0) return p[sz]*=-1,c=*this+b,c.p[c.sz]*=-1,c;else if(b<0) return b*=-1,*this+b;return c=*this-(c=b),c.p[c.sz]*=fu,c;}
		inline Big operator-(const LL &d){Big c;LL b=d;int fu=1;if(p[sz]<0 && b<0) p[sz]*=-1,b*=-1,fu*=-1;else if(p[sz]<0) return p[sz]*=-1,c=*this+b,c.p[c.sz]*=-1,c;else if(b<0) return b*=-1,*this+b;return c=*this-(c=b),c.p[c.sz]*=fu,c;}
		inline Big operator*(const Big &d){/*do something there*/}
		inline Big operator/(const int &d){Big a=*this, c;int b=d;int fu=1;if(a.p[a.sz]<0) a.p[a.sz]*=-1,fu*=-1;if(b<0) b*=-1,fu*=-1;LL x=0;if(b==0) return c;for(int i=a.sz;i;i=~-i)x=x*Mod+a.p[i],c.p[i]=x/b,x=x%b;for(c.sz=a.sz;c.p[c.sz]==0 && c.sz>1;c.sz--);return c.p[c.sz]*=fu,c;}
		inline Big operator/(const LL &d){Big a=*this,c;LL b=d;int fu=1;if(a.p[a.sz]<0) a.p[a.sz]*=-1,fu*=-1;if(b<0) b*=-1,fu*=-1;LL x=0;if(b==0) return c;for(int i=a.sz;i;i=~-i)x=x*Mod+a.p[i],c.p[i]=x/b,x=x%b;for(c.sz=a.sz;c.p[c.sz]==0 && c.sz>1;--c.sz);return c.p[c.sz]*=fu,c;}
		inline Big operator/(const Big &d){Big a=*this,b=d,c,ce;int fu=1;if(a.p[a.sz]<0) a.p[a.sz]*=-1,fu*=-1;if(b.p[b.sz]<0) b.p[b.sz]*=-1,fu*=-1;if(b.sz==1 && b.p[b.sz]==0) return c;if(a<b) return c=0;if(a==b) return c=1;if(b.sz<2) return a/b.toLL(fu);for(int i=a.sz;i;i=~-i){for(int j=++ce.sz;j>1;--j) ce.p[j]=ce.p[j-1];ce.p[1]=a.p[i];if(ce<b) continue;int l=0,r=Mod,x;while(l<=r){int mid=l+r>>1;if(b*mid<=ce) x=mid,l=mid+1;else r=mid-1;}c.p[i]=x,ce=ce-b*x;}for(c.sz=a.sz;c.p[c.sz]==0 && c.sz>1;c.sz--);return c.p[c.sz]*=fu,c;}
		inline Big operator%(const int &d){Big a=*this,c;int b=d;int fu=1;if(a.p[a.sz]<0) a.p[a.sz]*=-1,fu*=-1;if(b<0) b*=-1,fu*=-1;LL x=0;if(d==0) return c;for(int i=a.sz;i;i=~-i)x=(x*Mod+a.p[i])%b;return c=x*fu;}
		inline Big operator%(const LL &d){Big a=*this, c;LL b=d;int fu=1;if(a.p[a.sz]<0) a.p[a.sz]*=-1,fu*=-1;if(b<0) b*=-1,fu*=-1;LL x=0;if(d==0) return c;for(int i=a.sz;i;i=~-i) x=(x*Mod+a.p[i]) % b;return c=x*fu;}
		inline Big operator%(const Big &d){Big a=*this,b=d,ce;int fu=1;if(a.p[a.sz]<0) a.p[a.sz]*=-1,fu*=-1;if(b.p[b.sz]<0) b.p[b.sz]*=-1,fu*=-1;if(b.sz==1 && b.p[b.sz]==0) return ce;if(a<b) return a;if(a==b) return ce=0;if(b.sz<2) return a % b.toLL(fu);for(int i=a.sz;i; i=~-i){if(!(ce.sz==1 && ce.p[ce.sz]==0)) for(int j=++ce.sz; j>1; --j) ce.p[j]=ce.p[j-1];ce.p[1]=a.p[i];if(ce<b) continue;int l=0,r=Mod,x;while(l<=r){int mid=l+r>>1;if(ce<b*mid)r=mid-1;else x=mid,l=mid+1;}ce=ce-b*x;}return ce.p[ce.sz]*=fu,ce;} 
	public:
		inline Big operator+=(int &b){return *this=*this+b;}inline Big operator+=(LL &b){return *this=*this+b;}inline Big operator+=(Big &b){return *this=*this+b;} 
		inline Big operator++(void){return *this=*this+1;}inline Big operator--(void){return *this=*this-1;}
		inline Big operator-=(int &b){return *this=*this-b;}inline Big operator-=(LL &b){return *this=*this-b;}inline Big operator-=(Big &b){return *this=*this-b;} 
		inline Big operator*=(int &b){return *this=*this*b;}inline Big operator*=(LL &b){return *this=*this*b;}inline Big operator*=(Big &b){return *this=*this*b;}
		inline Big operator/=(int &b){return *this=*this/b;}inline Big operator/=(LL &b){return *this=*this/b;}inline Big operator/=(Big &b){return *this=*this/b;} 
		inline Big operator%=(int &b){return *this=*this%b;}inline Big operator%=(LL &b){return *this=*this%b;}inline Big operator%=(Big &b){return *this=*this%b;} 
		inline bool operator<(const int &b) const{Big c;return *this<(c=b);}inline bool operator<(const LL &b) const{Big c;return *this<(c=b);}inline bool operator<(const Big &b) const{if(sz^b.sz)return sz<b.sz;for (int i=sz;i; i=~-i) if(p[i]^b.p[i]) return p[i]<b.p[i];return false;} 
		inline bool operator<=(const int &b) const{Big c;return *this<=(c=b);}inline bool operator<=(const LL &b) const{Big c;return *this<=(c=b);}inline bool operator<=(const Big &b) const{if(sz^b.sz)return sz<b.sz;for (int i=sz;i; i=~-i) if(p[i]^b.p[i]) return p[i]<b.p[i];return true;} 
		inline bool operator>(const int &b) const{Big c;return *this>(c=b);}inline bool operator>(const LL &b) const{Big c;return *this>(c=b);}inline bool operator>(const Big &b) const{if(sz^b.sz)return sz>b.sz;for (int i=sz;i; i=~-i) if(p[i]^b.p[i]) return p[i]>b.p[i];return false;} 
		inline bool operator>=(const int &b) const{Big c;return *this>=(c=b);}inline bool operator>=(const LL &b) const{Big c;return *this>=(c=b);}inline bool operator>=(const Big &b) const{if(sz^b.sz)return sz>b.sz;for (int i=sz;i; i=~-i) if(p[i]^b.p[i]) return p[i]>b.p[i];return true;} 
		inline bool operator==(const int &b) const{Big c;return *this==(c=b);}inline bool operator==(const LL &b) const{Big c;return *this==(c=b);}inline bool operator==(const Big &b) const{if(sz^b.sz)return false;for(int i=sz;i; i=~-i) if(p[i]^b.p[i]) return false;return true;} 
		inline bool operator!=(const int &b) const{Big c;return *this!=(c=b);}inline bool operator!=(const LL &b) const{Big c;return *this!=(c=b);}inline bool operator!=(const Big &b) const{if(sz^b.sz)return true;for(int i=sz;i; i=~-i) if(p[i]^b.p[i]) return true;return false;} 
	public:
		Big(){clear();} 
		Big(int x){*this=x;} 
		Big(LL x){*this=x;} 
		inline void clear(void){sz=0;memset(p,0,sizeof p);} 
		inline void swap(Big &b){Big c=*this;*this=b;b=c;} 
		LL toLL(int fu=1){LL x=0;if(p[sz]<0) p[sz]*=-1,fu=-1;for(int i=sz;i;i=~-i) x=x*Mod+p[i];return x*fu;}
};
inline istream&operator>>(istream &in,register Big &x){return x.in(),cin;}
inline ostream&operator<<(ostream &out,register Big x){return x.out(),out;}
int main(void){
	Big a,b;
	cin>>a>>b;
	cout<<a*b;
}

完成者获得一个小粉粉~

2024/9/4 21:18
加载中...