高精度乘法模板(fft）

 正常高精度复杂度是o(n^2)，fft复杂度o(nlogn)

#define int long long//__int128 2^127-1(GCC)
#define PII pair<int,int>
#define f first
#define s second
using namespace std;
const int inf = 0x3f3f3f3f3f3f3f3f, N = 3e5 + 5, mod = 1e9 + 7;
const double PI = acos(-1);
int n, m;
struct Complex
{double x, y;Complex operator+ (const Complex& t) const{return { x + t.x, y + t.y };}Complex operator- (const Complex& t) const{return { x - t.x, y - t.y };}Complex operator* (const Complex& t) const{return { x * t.x - y * t.y, x * t.y + y * t.x };}
}a[N], b[N];int rev[N], bit, tot;
void fft(Complex a[], int inv)
{for (int i = 0; i < tot; i++)if (i < rev[i])swap(a[i], a[rev[i]]);for (int mid = 1; mid < tot; mid <<= 1){auto w1 = Complex({ cos(PI / mid), inv * sin(PI / mid) });for (int i = 0; i < tot; i += mid * 2){auto wk = Complex({ 1, 0 });for (int j = 0; j < mid; j++, wk = wk * w1){auto x = a[i + j], y = wk * a[i + j + mid];a[i + j] = x + y, a[i + j + mid] = x - y;}}}
}
signed main() {ios_base::sync_with_stdio(0);cin.tie(0), cout.tie(0);string aa, bb;cin >> aa >> bb;n = aa.size()-1, m = bb.size()-1;for (int i = 0; i <= n; i++) { a[i].x = aa[i] - '0'; }for (int i = 0; i <= m; i++) { b[i].x = bb[i] - '0'; }while ((1 << bit) < n + m + 1) bit++;tot = 1 << bit;for (int i = 0; i < tot; i++) {rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));}fft(a, 1), fft(b, 1);for (int i = 0; i < tot; i++) a[i] = a[i] * b[i];fft(a, -1);string s;int t=0;for (int i = n+m; i >= 0; i--) {t+=(int)(a[i].x / tot + 0.5);s+=t%10+'0';t/=10;}if(t) s+=t+'0';reverse(s.begin(),s.end());cout<<s;
}