高精度乘法模板(fft）-Toy模板网

这篇具有很好参考价值的文章主要介绍了高精度乘法模板(fft）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

正常高精度复杂度是o(n^2)，fft复杂度o(nlogn)文章来源地址https://www.toymoban.com/news/detail-695291.html

#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;
}

到了这里，关于高精度乘法模板(fft）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！