乘法学会fft以后，应该乘除都能优化很多。。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
int mi[28];
const int maxlen=2e5+16, maxbit=1e8;
int max(int a, int b) { return a<b?b:a; }
struct Bigint{
int flag, len, a[maxlen/8];
Bigint(){ memset(a, 0, sizeof(a)); len=0; flag=0; }
void shift(){
for (int i=len++; i>0; --i)
a[i]=a[i-1];
a[0]=0;
}
void plus1(){
++a[0];
for (int i=0; i<len; ++i)
if (a[i]>=maxbit) a[i]-=maxbit, ++a[i+1];
if (a[len]) ++len;
}
};
//并不是函数传出来的东西不能引用，而是c++不允许临时量被非常量引用
//因为不然你可以改变临时量，这很奇怪
bool operator <(const Bigint &a, const Bigint &b){
if (a.len!=b.len) return a.len<b.len;
for (int i=a.len-1; i>=0; --i)
if (a.a[i]!=b.a[i]) return a.a[i]<b.a[i];
return false;
}
bool operator <=(const Bigint &a, const Bigint &b){
if (a.len!=b.len) return a.len<b.len;
for (int i=a.len-1; i>=0; --i)
if (a.a[i]!=b.a[i]) return a.a[i]<b.a[i];
return true;
}
istream& operator >>(istream &in, Bigint &x){
char s[maxlen]; scanf("%s", s);
int len=strlen(s), count=(len-1)%8+1, j=0, now=(len-1)/8;
for (int i=0; i<len; ++i){
j=j*10+s[i]-48;
if (!--count) count=8, x.a[now--]=j, j=0;
}
x.len=(len-1)/8+1;
return in;
}
ostream& operator <<(ostream &out, const Bigint &x){
if (x.flag) printf("-");
printf("%d", x.a[x.len-1]);
for (int i=x.len-2; i>=0; --i)
printf("%08d", x.a[i]);
return out;
}
Bigint operator +(const Bigint &x, const Bigint &y){
int maxlen=max(x.len, y.len);
Bigint re;
for (int i=0; i<maxlen; ++i){
re.a[i]+=x.a[i]+y.a[i];
if (re.a[i]>=maxbit) re.a[i+1]+=1, re.a[i]-=maxbit;
}
if (re.a[maxlen]) re.len=maxlen+1;
else re.len=maxlen;
return re;
}
//目前减法只处理自然数
Bigint operator -(const Bigint &a, const Bigint &b){
bool less=false; if (a<b) less=true;
const Bigint &x=less?b:a, &y=less?a:b;
Bigint re; if (less) re.flag=1;
for (int i=0; i<x.len; ++i){
re.a[i]+=x.a[i]-y.a[i];
if (re.a[i]<0) re.a[i]+=maxbit, re.a[i+1]-=1;
}
//注意a=b
for (re.len=x.len; re.len&&!re.a[re.len-1]; --re.len);
return re;
}
//O(n)双对单
Bigint operator *(const Bigint &x, int y){
Bigint re;
for (int i=0; i<x.len; ++i){
long long t=re.a[i]+x.a[i]*(long long)y;
re.a[i+1]+=t/maxbit, re.a[i]=t%maxbit;
}
for (re.len=x.len; re.a[re.len]; ++re.len);
return re;
}
//n^2辣鸡算法，还不会傅里叶
Bigint operator *(const Bigint &x, const Bigint &y){
Bigint re;
for (int i=0; i<x.len; ++i)
for (int j=0; j<y.len; ++j){
long long t=re.a[i+j]+(long long)x.a[i]*y.a[j];
re.a[i+j+1]+=t/maxbit, re.a[i+j]=t%maxbit;
}
if (re.a[x.len+y.len-1]) re.len=x.len+y.len;
else re.len=x.len+y.len-1;
return re;
}
//n^2双对单除法
Bigint operator /(const Bigint &x, int y){
Bigint re; re.len=x.len;
long long tmp=0;
for (int i=x.len-1; i>=0; --i){
tmp=tmp*maxbit+x.a[i];
re.a[i]=tmp/y; tmp=tmp%y;
}
for (; re.len>0&&!re.a[re.len-1]; --re.len);
return re;
}
//n^2log1e8双高精除法(fft后可以到nlog1e8)
Bigint operator /(const Bigint &x, const Bigint &y){
Bigint re; re.len=x.len;
Bigint tmp;
for (int i=x.len-1; i>=0; --i){
tmp.shift(); tmp.a[0]=x.a[i];
//for (; !(tmp<y); tmp=tmp-y, ++re.a[i]);
for (int j=27; j>=0; --j){
if (y*mi[j]<=tmp)
tmp=tmp-y*mi[j], re.a[i]+=mi[j];
}
}
for (; re.len>0&&!re.a[re.len-1]; --re.len);
return re;
}
Bigint operator %(const Bigint &x, const Bigint &y){
Bigint re; re.len=x.len;
Bigint tmp;
for (int i=x.len-1; i>=0; --i){
tmp.shift(); tmp.a[0]=x.a[i];
//for (; !(tmp<y); tmp=tmp-y, ++re.a[i]);
for (int j=27; j>=0; --j){
if (y*mi[j]<=tmp)
tmp=tmp-y*mi[j], re.a[i]+=mi[j];
}
}
return tmp;
}
void init(){
mi[0]=1;
for (int i=1; i<27; ++i)
mi[i]=mi[i-1]*2;
}
Bigint a, b;
int main(){
init();
cin>>a>>b;
cout<<a+b<<endl<<a-b<<endl<<a*b<<endl<<a/b<<endl<<a%b;
return 0;
}