FFT

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

long long mod(long long x, long long mod)
{
    return ((x % mod) + mod) % mod;
}

long long bin_pow_mod(long long a, long long b, long long mod)
{
    if (b == 0)
        return 1;
    if (b == 1)
        return a % mod;
    if (b % 2 == 0)
    {
        long long x = bin_pow_mod(a, b / 2, mod) % mod;
        return (x * x) % mod;
    }
    else
        return (a * bin_pow_mod(a, b - 1, mod) ) % mod;
}

vector <long long> to_binary(long long a)
{
    vector <long long> ans;
    while (a > 0)
    {
        ans.push_back(a % 2);
        a /= 2;
    }
    reverse(ans.begin(), ans.end());
    return ans;
}

long long rev(long long x, long long k, long long m)
{
    long long ans = 0;
    vector <int> vec(k);
    long long i = 0;
    while (x > 0)
    {
        vec[i] = x % 2;
        x /= 2;
        i++;
    }
    long long d = 0;
    for (i = k - 1; i >= 0; i--)
        ans += vec[i] * bin_pow_mod(2, (d++), m);
    return ans;
}

long long inserted_digit(long long digit, long long i, long long l, long long count_of_bits, long long m)
{
    vector<int> vec_i(count_of_bits);
    long long w = 0;
    while (i > 0)
    {
        vec_i[w] = i % 2;
        i /= 2;
        w++;
    }
    vec_i[l] = digit;
    long long d = 0, ans = 0;
    for (long long qq = 0; qq < count_of_bits; qq++)
        ans += vec_i[qq] * bin_pow_mod(2, (d++), m);
    return ans;
}

long long extended_euclid(long long a, long long b, long long& x, long long& y)
{
    if (a == 0)
    {
        x = 0;
        y = 1;
        return b;
    }
    long long x1, y1;
    long long d = extended_euclid(b % a, a, x1, y1);
    x = y1 - (b / a) * x1;
    y = x1;
    return d;
}

long long reverse_element(long long a, long long m)
{
    long long x, y;
    long long g = extended_euclid(a, m, x, y);
    if (g != 1)
    {
        cout << a << " не имеет обратного элемента по модулю " << m << endl;
        exit(0);
    }
    else
    {
        x = mod(x, m);
        return x;
    }
}

vector <long long> FFT(long long n, long long k, vector<long long> a, long long w, long long m)
{
    vector <long long> b(n), s(n), r(n);
    // 1
    for (long long i = 0; i < n; i++)
        r[i] = a[i];
    // 2
    for (long long l = k - 1; l >= 0; l--)
    {
        for (long long i = 0; i < n; i++)
            s[i] = r[i];
        for (long long i = 0; i < n; i++)
        {
            long long s0 = inserted_digit(0, i, l, k, m);
            long long revi = rev(i / bin_pow_mod(2, l, m), k, m);
            long long s1 = inserted_digit(1, i, l, k, m);
            r[i] = s[s0] + bin_pow_mod(w, revi, m) * s[s1];
            r[i] = mod(r[i], m);
        }
    }
    // 3
    for (long long i = 0; i < n; i++)
    {
        b[i] = r[rev(i, k, m)];
    }
    return b;
}

vector <long long> reverse_FFT(long long n, long long k, vector<long long> a, long long w_1, long long m, long long n_1)
{
    vector <long long> b(n), s(n), r(n);
    // 1
    for (long long i = 0; i < n; i++)
        r[i] = a[i];
    // 2
    for (long long l = k - 1; l >= 0; l--)
    {
        for (long long i = 0; i < n; i++)
            s[i] = r[i];
        for (long long i = 0; i < n; i++)
        {
            long long s0 = inserted_digit(0, i, l, k, m);
            long long revi = rev(i / bin_pow_mod(2, l, m), k, m);
            long long s1 = inserted_digit(1, i, l, k, m);
            r[i] = s[s0] + bin_pow_mod(w_1, revi, m) * s[s1];
            r[i] = mod(r[i], m);
        }
    }
    // 3
    for (long long i = 0; i < n; i++)
    {
        b[i] = n_1 * r[rev(i, k, m)];
        b[i] = mod(b[i], m);
    }
    return b;
}

vector <long long> divide(vector<long long> v, long long N, long long L)
{
    vector <long long> ans;
    reverse(v.begin(), v.end());
    while (v.size() < N)
        v.push_back(0);
    long long sum = 0, d = 1;
    for (int i = 0; i < v.size(); i++)
    {
        sum += v[i] * d;
        d *= 2;
        if (i % L == L - 1)
        {
            ans.push_back(sum);
            sum = 0;
            d = 1;
        }
    }
    if (sum > 0)
        ans.push_back(sum);
    return ans;
}

long long SS(vector <long long> u, vector <long long> v, long long n, long long N)
{
    // 1
    long long l = n/2, k = n - l, K = bin_pow_mod(2, k, LONG_MAX), L = bin_pow_mod(2, l, LONG_MAX);
    u = divide(u, N, L);
    v = divide(v, N, L);
    // 2
    vector <long long> W(u.size()), W_(u.size());
    for (long long i = 0; i < K; i++)
    {
        long long sum1 = 0, sum2 = 0;
        for (long long j = 0; j <= i; j++)
            sum1 += u[i - j] * v[j];
        for (long long j = i + 1; j < K; j++)
            sum2 += u[i + K - j] * v[j];
        W[i] = sum1 - sum2;
        W_[i] = mod(W[i], K);
    }
    // 3
    vector <long long> W__(u.size());
    long long psi = bin_pow_mod(2, 2*L/K, LONG_MAX);
    vector <long long> u_(u.size()), v_(u.size());
    long long pr = 1;
    for (long long i = 0; i < u.size(); i++)
    {
        u_[i] = u[i] * pr;
        v_[i] = v[i] * pr;
        if (i != u.size() - 1)
            pr *= psi;
    }
    long long m = bin_pow_mod(2, 2 * L, LONG_MAX) + 1;
    long long w = bin_pow_mod(2, 4 * L/K, LONG_MAX);

    vector <long long> u__ = FFT(u.size(), log(u.size() * 1.0) / log(2.0), u_, w, m);
    vector <long long> v__ = FFT(v.size(), log(v.size() * 1.0) / log(2.0), v_, w, m);

    vector <long long> c(u.size());
    for (long long i = 0; i < u.size(); i++)
        c[i] = mod(u__[i] * v__[i], m);

    long long w_1 = -1 * bin_pow_mod(2, 2 * L - 4 * L / K, LONG_MAX);
    vector <long long> d = reverse_FFT(c.size(), log(c.size() * 1.0) / log(2.0), c, mod(w_1, m), m, reverse_element(c.size(), m));

    long long psi_1 = -1 * bin_pow_mod(2, 2 * L - 2 * L / K, LONG_MAX);
    pr = 1;
    for (long long i = 0; i < d.size(); i++)
    {
        W__[i] = mod(d[i] * pr, m);
        pr *= psi_1;
    }
    // 4
    for (long long i = 0; i < K; i++)
    {
        long long W___ = (bin_pow_mod(2, 2 * L, LONG_MAX) + 1) * (mod(W_[i] - W__[i], K)) + W__[i];
        if (W___ < (i+1) * bin_pow_mod(2, 2 * L, LONG_MAX))
            W[i] = W___;
        else
            W[i] = W___ - K * (bin_pow_mod(2, 2 * L, LONG_MAX) + 1);
    }
    // 5
    long long y = 0;
    for (long long i = 0; i < W.size(); i++)
        y += W[i] * bin_pow_mod(2, L * i, LONG_MAX);
    return y;
}

int main()
{
    setlocale(LC_ALL, "RUSSIAN");
    int mode;
    cout << "Введите 1 или 2: 1 - для запуска быстрого преобразования Фурье и обратного быстрого преобразования Фурье, 2 - для запуска алгоритма Шенхаге-Штрассена: ";
    cin >> mode;
    if (mode == 1)
    {
        long long n;
        cout << "Введите n: ";
        cin >> n;

        long long n1 = n, count = 0;
        while (n1 != 1)
        {
            count++;
            n1 /= 2;
        }
        long long k = count;

        vector <long long> a(n), b(n);
        cout << "Введите элементы массива а: ";
        for (long long i = 0; i < n; i++)
            cin >> a[i];

        long long w = 2;
        cout << "Преобразованный массив: ";
        long long m = bin_pow_mod(w, n/2, LONG_MAX) + 1;
        b = FFT(n, k, a, w, m);
        for (long long i = 0; i < n; i++)
            cout << b[i] << " ";
        cout << endl;

        cout << "Обратно преобразованный массив: ";
        a = reverse_FFT(n, k, b, reverse_element(w, m), m, reverse_element(n, m));
        for (long long i = 0; i < n; i++)
            cout << a[i] << " ";
        cout << endl;
    }
    else
        if (mode == 2)
        {
            long long a, b;
            cout << "Введите два числа: ";
            cin >> a >> b;

            vector <long long> aa = to_binary(a), bb = to_binary(b);
            long long n = 7;
            long long y = SS(aa, bb, n, bin_pow_mod(2, n, LONG_MAX));
            cout << "Результат умножения чисел: " << y << endl;
        }

    return 0;
}