https://www.luogu.com.cn/problem/P1932
待补:压位高精,多项式除法优化除法、取模
高精度除可以钦定选取前几位后再进行除法（也许常数略小？）
Luogu1932 A+B A-B A*B A/B A%B Problem
注意：使用时需要在开头调用Pre函数，见主程序第一行
高精度合集(vector)
NTT优化乘法,vector,无符号
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#define N 20005
#define M 40005
#define ll long long
#define a hz.w
#define b kz.w
#define c kzkz.w
#define d kzzf.w
#define P 998244353
#define inv(x) ksm(x,P-2)
#define zero(x) (x.w[0]==1 && x.w[1]==0)
#define IT vector<int> :: iterator
using namespace std;
char orz[N];
int rev[M];
int G[2][25];
int e[M],f[M];
int ksm(int x,int y);
void NTT(int *g,int t,int s);
struct BigNumber
{
vector<int>w;
void set0()
{
w.clear();
w.push_back(1),w.push_back(0);
}
void set1()
{
w.clear();
w.push_back(1),w.push_back(1);
}
void setNum(ll x)
{
if (!x)
{
set0();
return;
}
w.clear();
w.push_back(0);
int g=0;
while (x)
{
w.push_back(x%10);
x/=10;
g++;
}
w[0]=g;
}
void read()
{
scanf("%s",orz);
w.clear();
w.push_back(strlen(orz));
for (int i=w[0]-1;i>=0;i--)
w.push_back(orz[i]-'0');
}
}s,t;
BigNumber kz,kzkz,kzzf;
void write(BigNumber kz)
{
for (int i=b[0];i>=1;i--)
putchar(b[i]+'0');
putchar('\n');
}
bool operator < (BigNumber hz,BigNumber kz)
{
if (a[0]!=b[0])
return a[0]<b[0];
for (int i=a[0];i>=1;i--)
if (a[i]!=b[i])
return a[i]<b[i];
return false;
}
bool operator <= (BigNumber hz,BigNumber kz)
{
if (a[0]!=b[0])
return a[0]<b[0];
for (int i=a[0];i>=1;i--)
if (a[i]!=b[i])
return a[i]<b[i];
return true;
}
bool operator > (BigNumber hz,BigNumber kz)
{
if (a[0]!=b[0])
return a[0]>b[0];
for (int i=a[0];i>=1;i--)
if (a[i]!=b[i])
return a[i]>b[i];
return false;
}
bool operator >= (BigNumber hz,BigNumber kz)
{
if (a[0]!=b[0])
return a[0]>b[0];
for (int i=a[0];i>=1;i--)
if (a[i]!=b[i])
return a[i]>b[i];
return true;
}
bool operator == (BigNumber hz,BigNumber kz)
{
if (a[0]!=b[0])
return false;
for (int i=a[0];i>=1;i--)
if (a[i]!=b[i])
return false;
return true;
}
bool operator != (BigNumber hz,BigNumber kz)
{
if (a[0]!=b[0])
return true;
for (int i=a[0];i>=1;i--)
if (a[i]!=b[i])
return true;
return false;
}
BigNumber operator + (BigNumber hz,BigNumber kz)
{
int ws=max(a[0],b[0]);
int jw=0;
for (int i=1;i<=ws;i++)
{
if (b[0]<i)
{
b[0]++;
b.push_back(0);
}
if (a[0]>=i)
b[i]+=a[i];
b[i]+=jw;
jw=b[i]/10;
b[i]%=10;
}
while (jw)
{
b[0]++;
b.push_back(jw%10);
jw/=10;
}
return kz;
}
BigNumber operator - (BigNumber hz,BigNumber kz)
{
int ws=max(a[0],b[0]);
for (int i=1;i<=ws;i++)
{
if (b[0]<i)
b.push_back(a[i]); else
b[i]=a[i]-b[i];
if (b[i]<0)
{
b[i]+=10;
a[i+1]--;
}
}
IT it=b.end()-1;
while (!(*it) && ws>1)
{
ws--;
b.erase(it--);
}
b[0]=ws;
return kz;
}
BigNumber operator * (BigNumber hz,BigNumber kz)
{
if (zero(hz) || zero(kz))
{
hz.set0();
return hz;
}
int la=a[0],lb=b[0];
int s=1,l=0;
while (s<la+lb)
{
s <<=1;
l++;
}
rev[0]=0;
for (int i=1;i<s;i++)
rev[i]=(rev[i >> 1] >> 1) | ((i & 1) << (l - 1));
e[0]=f[0]=0;
for (int i=1;i<=la;i++)
e[i-1]=a[i];
for (int i=1;i<=lb;i++)
f[i-1]=b[i];
for (int i=la;i<s;i++)
e[i]=0;
for (int i=lb;i<s;i++)
f[i]=0;
NTT(e,0,s);
NTT(f,0,s);
for (int i=0;i<s;i++)
e[i]=(ll)e[i]*f[i]%P;
NTT(e,1,s);
int invs=inv(s);
for (int i=s;i>=1;i--)
e[i]=(ll)e[i-1]*invs%P;
e[0]=0;
for (int i=1;i<=la+lb;i++)
{
e[i+1]+=e[i]/10;
e[i]%=10;
}
a[0]=la+lb;
while (!e[a[0]] && a[0]>1)
a[0]--;
for (int i=1;i<=a[0];i++)
if (la<i)
a.push_back(e[i]); else
a[i]=e[i];
return hz;
}
BigNumber operator / (BigNumber hz,BigNumber kz)
{
c.clear();
c.push_back(0);
for (int i=1;i<=a[0];i++)
c.push_back(0);
c[0]=a[0];
kzzf.set0();
for (int i=a[0];i>=1;i--)
{
if (!(d[0]==1 && d[1]==0))
{
d.push_back(0);
for (int i=d[0];i>=1;i--)
d[i+1]=d[i];
d[1]=a[i];
d[0]++;
} else
d[1]=a[i];
while (kzzf>=kz)
{
kzzf=kzzf-kz;
c[i]++;
}
}
IT it=c.end()-1;
while (!(*it) && c[0]>1)
{
c[0]--;
c.erase(it--);
}
return kzkz;
}
BigNumber operator % (BigNumber hz,BigNumber kz)
{
kzzf.set0();
for (int i=a[0];i>=1;i--)
{
if (!(d[0]==1 && d[1]==0))
{
d.push_back(0);
for (int i=d[0];i>=1;i--)
d[i+1]=d[i];
d[1]=a[i];
d[0]++;
} else
d[1]=a[i];
while (kzzf>=kz)
kzzf=kzzf-kz;
}
return kzzf;
}
void operator += (BigNumber &kz,BigNumber hz)
{
kz=kz+hz;
}
void operator -= (BigNumber &kz,BigNumber hz)
{
kz=kz-hz;
}
void operator *= (BigNumber &kz,BigNumber hz)
{
kz=kz*hz;
}
void operator /= (BigNumber &kz,BigNumber hz)
{
kz=kz/hz;
}
void operator %= (BigNumber &kz,BigNumber hz)
{
kz=kz%hz;
}
BigNumber Number_Turn_BigNumber(ll x)
{
if (x==0)
{
kz.set0();
return kz;
}
b.clear();
b.push_back(0);
while (x)
{
b[0]++;
b.push_back(x%10);
x/=10;
}
return kz;
}
ll BigNumber_Turn_Number(BigNumber kz)
{
ll y=0;
for (int i=b[0];i>=1;i--)
y=y*10+b[i];
return y;
}
void NTT(int *q,int t,int s)
{
for (int i=0;i<s;i++)
if (i<rev[i])
swap(q[i],q[rev[i]]);
for (int mid=1,o=1;mid<s;mid <<=1,o++)
for (int j=0;j<s;j+=(mid << 1))
{
int g=1;
for (int k=0;k<mid;k++,g=(ll)g*G[t][o]%P)
{
int x=q[j+k],y=(ll)g*q[j+k+mid]%P;
q[j+k]=(x+y)%P;
q[j+k+mid]=(x-y+P)%P;
}
}
}
int ksm(int x,int y)
{
int ans=1;
while (y)
{
if (y & 1)
ans=(ll)ans*x%P;
x=(ll)x*x%P;
y >>=1;
}
return ans;
}
void Pre()
{
G[0][23]=ksm(3,(P-1)/(1 << 23));
G[1][23]=inv(G[0][23]);
for (int i=22;i>=1;i--)
{
G[0][i]=(ll)G[0][i+1]*G[0][i+1]%P;
G[1][i]=(ll)G[1][i+1]*G[1][i+1]%P;
}
}
int main()
{
Pre();
s.read(),t.read();
write(s+t);
if (s<t)
putchar('-'),write(t-s); else
write(s-t);
write(s*t);
write(s/t);
write(s%t);
return 0;
}
NTT优化乘法,vector,带符号
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#define N 20005
#define M 40005
#define ll long long
#define a hz.w
#define b kz.w
#define c kzkz.w
#define d kzzf.w
#define hp hz.p
#define kp kz.p
#define cp kzkz.p
#define dp kzzf.p
#define P 998244353
#define inv(x) ksm(x,P-2)
#define zero(x) (x.w[0]==1 && x.w[1]==0)
#define IT vector<int> :: iterator
using namespace std;
char orz[N];
int rev[M];
int G[2][25];
int e[M],f[M];
int ksm(int x,int y);
void NTT(int *g,int t,int s);
struct BigNumber
{
vector<int>w;
bool p=true;
void set0()
{
w.clear();
w.push_back(1),w.push_back(0);
p=true;
}
void set1()
{
w.clear();
w.push_back(1),w.push_back(1);
p=true;
}
void read()
{
scanf("%s",orz);
w.clear();
w.push_back(strlen(orz));
if (orz[0]=='-')
{
p=false;
w[0]--;
for (int i=w[0];i>=1;i--)
w.push_back(orz[i]-'0');
} else
{
p=true;
for (int i=w[0]-1;i>=0;i--)
w.push_back(orz[i]-'0');
}
}
}s,t;
BigNumber kz,kzkz,kzzf;
void write(BigNumber kz)
{
if (!kz.p)
putchar('-');
for (int i=b[0];i>=1;i--)
putchar(b[i]+'0');
putchar('\n');
}
bool operator > (BigNumber hz,BigNumber kz);
bool operator < (BigNumber hz,BigNumber kz)
{
if (hp!=kp)
return kp;
if (!hp)
{
hp=kp=true;
return hz>kz;
}
if (a[0]!=b[0])
return a[0]<b[0];
for (int i=a[0];i>=1;i--)
if (a[i]!=b[i])
return a[i]<b[i];
return false;
}
bool operator >= (BigNumber hz,BigNumber kz);
bool operator <= (BigNumber hz,BigNumber kz)
{
if (hp!=kp)
return kp;
if (!hp)
{
hp=kp=true;
return hz>=kz;
}
if (a[0]!=b[0])
return a[0]<b[0];
for (int i=a[0];i>=1;i--)
if (a[i]!=b[i])
return a[i]<b[i];
return true;
}
bool operator > (BigNumber hz,BigNumber kz)
{
if (hp!=kp)
return hp;
if (!hp)
{
hp=kp=true;
return hz<kz;
}
if (a[0]!=b[0])
return a[0]>b[0];
for (int i=a[0];i>=1;i--)
if (a[i]!=b[i])
return a[i]>b[i];
return false;
}
bool operator >= (BigNumber hz,BigNumber kz)
{
if (hp!=kp)
return hp;
if (!hp)
{
hp=kp=true;
return hz<=kz;
}
if (a[0]!=b[0])
return a[0]>b[0];
for (int i=a[0];i>=1;i--)
if (a[i]!=b[i])
return a[i]>b[i];
return true;
}
bool operator == (BigNumber hz,BigNumber kz)
{
if (hp!=kp)
return false;
if (a[0]!=b[0])
return false;
for (int i=a[0];i>=1;i--)
if (a[i]!=b[i])
return false;
return true;
}
bool operator != (BigNumber hz,BigNumber kz)
{
if (hp!=kp)
return true;
if (a[0]!=b[0])
return true;
for (int i=a[0];i>=1;i--)
if (a[i]!=b[i])
return true;
return false;
}
BigNumber operator - (BigNumber hz,BigNumber kz);
BigNumber operator + (BigNumber hz,BigNumber kz)
{
if (zero(hz))
return kz;
if (zero(kz))
return hz;
if (hp!=kp)
{
if (!kp)
{
kp=!kp;
return hz-kz;
} else
{
hp=!hp;
return kz-hz;
}
}
int ws=max(a[0],b[0]);
int jw=0;
for (int i=1;i<=ws;i++)
{
if (b[0]<i)
{
b[0]++;
b.push_back(0);
}
if (a[0]>=i)
b[i]+=a[i];
b[i]+=jw;
jw=b[i]/10;
b[i]%=10;
}
while (jw)
{
b[0]++;
b.push_back(jw%10);
jw/=10;
}
if (zero(kz))
kp=true;
return kz;
}
BigNumber operator - (BigNumber hz,BigNumber kz)
{
if (zero(kz))
return hz;
if (zero(hz))
{
kp=!kp;
return kz;
}
if (!hp && kp)
{
kp=!kp;
return hz+kz;
}
if (hp && !kp)
{
kp=!kp;
return hz+kz;
}
if (!hp && !kp)
{
hp=!hp,kp=!kp;
swap(hz,kz);
}
bool gk=true;
if (hz<kz)
{
gk=false;
swap(hz,kz);
}
int ws=max(a[0],b[0]);
for (int i=1;i<=ws;i++)
{
if (b[0]<i)
b.push_back(a[i]); else
b[i]=a[i]-b[i];
if (b[i]<0)
{
b[i]+=10;
a[i+1]--;
}
}
IT it=b.end()-1;
while (!(*it) && ws>1)
{
ws--;
b.erase(it--);
}
b[0]=ws;
if (!gk)
kp=!kp;
if (zero(kz))
kp=true;
return kz;
}
BigNumber operator * (BigNumber hz,BigNumber kz)
{
if (zero(hz) || zero(kz))
{
hz.set0();
return hz;
}
hp=!(hp^kp);
int la=a[0],lb=b[0];
int s=1,l=0;
while (s<la+lb)
{
s <<=1;
l++;
}
rev[0]=0;
for (int i=1;i<s;i++)
rev[i]=(rev[i >> 1] >> 1) | ((i & 1) << (l - 1));
e[0]=f[0]=0;
for (int i=1;i<=la;i++)
e[i-1]=a[i];
for (int i=1;i<=lb;i++)
f[i-1]=b[i];
for (int i=la;i<s;i++)
e[i]=0;
for (int i=lb;i<s;i++)
f[i]=0;
NTT(e,0,s);
NTT(f,0,s);
for (int i=0;i<s;i++)
e[i]=(ll)e[i]*f[i]%P;
NTT(e,1,s);
int invs=inv(s);
for (int i=s;i>=1;i--)
e[i]=(ll)e[i-1]*invs%P;
e[0]=0;
for (int i=1;i<=la+lb;i++)
{
e[i+1]+=e[i]/10;
e[i]%=10;
}
a[0]=la+lb;
while (!e[a[0]] && a[0]>1)
a[0]--;
for (int i=1;i<=a[0];i++)
if (la<i)
a.push_back(e[i]); else
a[i]=e[i];
return hz;
}
BigNumber operator / (BigNumber hz,BigNumber kz)
{
if (zero(hz))
{
kzkz.set0();
return kzkz;
}
if (hp!=kp)
cp=false; else
cp=true;
hp=kp=true;
c.clear();
c.push_back(0);
for (int i=1;i<=a[0];i++)
c.push_back(0);
c[0]=a[0];
kzzf.set0();
for (int i=a[0];i>=1;i--)
{
if (!(d[0]==1 && d[1]==0))
{
d.push_back(0);
for (int i=d[0];i>=1;i--)
d[i+1]=d[i];
d[1]=a[i];
d[0]++;
} else
d[1]=a[i];
while (kzzf>=kz)
{
kzzf=kzzf-kz;
c[i]++;
}
}
IT it=c.end()-1;
while (!(*it) && c[0]>1)
{
c[0]--;
c.erase(it--);
}
if (zero(kzkz))
cp=true;
return kzkz;
}
BigNumber operator % (BigNumber hz,BigNumber kz)
{
if (zero(hz))
{
kzzf.set0();
return kzzf;
}
bool gk;
gk=hp;
hp=kp=true;
kzzf.set0();
for (int i=a[0];i>=1;i--)
{
if (!(d[0]==1 && d[1]==0))
{
d.push_back(0);
for (int i=d[0];i>=1;i--)
d[i+1]=d[i];
d[1]=a[i];
d[0]++;
} else
d[1]=a[i];
while (kzzf>=kz)
kzzf=kzzf-kz;
}
dp=gk;
if (zero(kzzf))
dp=true;
return kzzf;
}
void operator += (BigNumber &kz,BigNumber hz)
{
kz=kz+hz;
}
void operator -= (BigNumber &kz,BigNumber hz)
{
kz=kz-hz;
}
void operator *= (BigNumber &kz,BigNumber hz)
{
kz=kz*hz;
}
void operator /= (BigNumber &kz,BigNumber hz)
{
kz=kz/hz;
}
void operator %= (BigNumber &kz,BigNumber hz)
{
kz=kz%hz;
}
BigNumber Number_Turn_BigNumber(ll x)
{
if (x==0)
{
kz.set0();
kp=true;
return kz;
}
if (x<0)
{
kp=false;
x=-x;
} else
kp=true;
b.clear();
b.push_back(0);
while (x)
{
b[0]++;
b.push_back(x%10);
x/=10;
}
return kz;
}
ll BigNumber_Turn_Number(BigNumber kz)
{
ll y=0;
for (int i=b[0];i>=1;i--)
y=y*10+b[i];
if (!kp)
y=-y;
return y;
}
void NTT(int *q,int t,int s)
{
for (int i=0;i<s;i++)
if (i<rev[i])
swap(q[i],q[rev[i]]);
for (int mid=1,o=1;mid<s;mid <<=1,o++)
for (int j=0;j<s;j+=(mid << 1))
{
int g=1;
for (int k=0;k<mid;k++,g=(ll)g*G[t][o]%P)
{
int x=q[j+k],y=(ll)g*q[j+k+mid]%P;
q[j+k]=(x+y)%P;
q[j+k+mid]=(x-y+P)%P;
}
}
}
int ksm(int x,int y)
{
int ans=1;
while (y)
{
if (y & 1)
ans=(ll)ans*x%P;
x=(ll)x*x%P;
y >>=1;
}
return ans;
}
void Pre()
{
G[0][23]=ksm(3,(P-1)/(1 << 23));
G[1][23]=inv(G[0][23]);
for (int i=22;i>=1;i--)
{
G[0][i]=(ll)G[0][i+1]*G[0][i+1]%P;
G[1][i]=(ll)G[1][i+1]*G[1][i+1]%P;
}
}
int main()
{
Pre();
s.read(),t.read();
write(s+t);
write(s-t);
write(s*t);
write(s/t);
write(s%t);
return 0;
}