#46287: cpp ans


1121232@stu.wghs.tp.edu.tw (Ian911436)

學校 : 臺北市私立薇閣高級中學
編號 : 258883
來源 : [60.248.154.143]
最後登入時間 :
2025-06-20 09:40:35

#include <bits/stdc++.h>
using namespace std;
using cd = complex<double>;
const double PI = acos(-1);

// FFT 變換,dir = 1 正向 FFT, dir = -1 反向 FFT
void fft(vector<cd> &a, int dir) {
    int n = (int)a.size();
    for (int i=1,j=0; i<n; i++) {
        int bit = n >> 1;
        for (; j & bit; bit >>=1) j ^= bit;
        j |= bit;
        if (i < j) swap(a[i], a[j]);
    }
    for (int len=2; len<=n; len<<=1) {
        double ang = 2*PI/len*dir;
        cd wlen(cos(ang), sin(ang));
        for (int i=0; i<n; i+=len) {
            cd w(1);
            for (int j=0; j<len/2; j++) {
                cd u = a[i+j], v = a[i+j+len/2]*w;
                a[i+j] = u+v;
                a[i+j+len/2] = u - v;
                w *= wlen;
            }
        }
    }
    if (dir == -1) {
        for (auto &x : a) x /= n;
    }
}

// FFT 大數乘法
string multiply_fft(const string &a, const string &b) {
    vector<int> A, B;
    for (int i = (int)a.size()-1; i >= 0; i--) A.push_back(a[i]-'0');
    for (int i = (int)b.size()-1; i >= 0; i--) B.push_back(b[i]-'0');

    int n = 1;
    while (n < (int)(A.size() + B.size())) n <<= 1;

    vector<cd> fa(A.begin(), A.end()), fb(B.begin(), B.end());
    fa.resize(n); fb.resize(n);

    fft(fa, 1);
    fft(fb, 1);
    for (int i=0; i<n; i++) fa[i] *= fb[i];
    fft(fa, -1);

    vector<int> res(n);
    int carry = 0;
    for (int i=0; i<n; i++) {
        long long val = (long long)(fa[i].real() + 0.5) + carry;
        res[i] = val % 10;
        carry = val / 10;
    }

    while (res.size() > 1 && res.back() == 0) res.pop_back();

    string result;
    for (int i = (int)res.size()-1; i >= 0; i--) result += (res[i] + '0');
    return result;
}

// 去除前導 0
string trim_leading_zeros(const string &s) {
    int i = 0;
    while (i < (int)s.size()-1 && s[i] == '0') i++;
    return s.substr(i);
}

// 大數加法
string add(const string &a, const string &b) {
    int n = (int)max(a.size(), b.size());
    string res;
    int carry = 0;
    for (int i = 0; i < n || carry; i++) {
        int x = i < (int)a.size() ? a[a.size() - 1 - i] - '0' : 0;
        int y = i < (int)b.size() ? b[b.size() - 1 - i] - '0' : 0;
        int sum = x + y + carry;
        carry = sum / 10;
        res.push_back(sum % 10 + '0');
    }
    reverse(res.begin(), res.end());
    return trim_leading_zeros(res);
}

// 大數比較 a >= b
bool is_greater_or_equal(string a, string b) {
    a = trim_leading_zeros(a);
    b = trim_leading_zeros(b);
    if (a.size() != b.size()) return a.size() > b.size();
    return a >= b;
}

// 大數減法 a - b (a >= b)
string subtract(string a, string b) {
    if (!is_greater_or_equal(a, b)) swap(a, b);
    int n = (int)a.size();
    string res(n, '0');
    int borrow = 0;
    for (int i = 0; i < n; i++) {
        int x = a[n - 1 - i] - '0' - borrow;
        int y = i < (int)b.size() ? b[b.size() - 1 - i] - '0' : 0;
        if (x < y) {
            x += 10;
            borrow = 1;
        } else {
            borrow = 0;
        }
        res[n - 1 - i] = (x - y) + '0';
    }
    return trim_leading_zeros(res);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string line;
    getline(cin, line);
    stringstream ss(line);

    string a, b; char op;
    ss >> a >> op >> b;

    string res;
    if (op == '+') res = add(a, b);
    else if (op == '-') res = subtract(a, b);
    else if (op == '*') res = multiply_fft(a, b);

    cout << res << "\n";
    return 0;
}

#46296: Re: cpp ans


1121232@stu.wghs.tp.edu.tw (Ian911436)

學校 : 臺北市私立薇閣高級中學
編號 : 258883
來源 : [60.248.154.143]
最後登入時間 :
2025-06-20 09:40:35

#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;
const int G = 3;

using VI = vector<int>;

int fastpow(int a, int b) {
    int res = 1;
    int base = a;
    while (b) {
        if (b & 1) res = (int)((int64_t)res * base % MOD);
        base = (int)((int64_t)base * base % MOD);
        b >>= 1;
    }
    return res;
}

void ntt(VI &a, bool invert) {
    int n = (int)a.size();
    for (int i = 1, j = 0; i < n; ++i) {
        int bit = n >> 1;
        for (; j & bit; bit >>= 1)
            j ^= bit;
        j ^= bit;
        if (i < j) swap(a[i], a[j]);
    }

    for (int len = 2; len <= n; len <<= 1) {
        int wlen = fastpow(G, (MOD - 1) / len);
        if (invert) wlen = fastpow(wlen, MOD - 2);
        for (int i = 0; i < n; i += len) {
            int w = 1;
            int half = len >> 1;
            for (int j = 0; j < half; ++j) {
                int u = a[i + j];
                int v = (int)((int64_t)a[i + j + half] * w % MOD);
                a[i + j] = u + v < MOD ? u + v : u + v - MOD;
                a[i + j + half] = u - v >= 0 ? u - v : u - v + MOD;
                w = (int)((int64_t)w * wlen % MOD);
            }
        }
    }

    if (invert) {
        int inv_n = fastpow(n, MOD - 2);
        for (int &x : a)
            x = (int)((int64_t)x * inv_n % MOD);
    }
}

VI parse(const string &s) {
    VI v(s.size());
    for (int i = 0; i < (int)s.size(); i++)
        v[(int)s.size() - 1 - i] = s[i] - '0';  // 反轉放好,後續不用再反轉
    return v;
}

VI add(const VI &a, const VI &b) {
    int n = (int)max(a.size(), b.size());
    VI res;
    res.reserve(n + 1);
    int carry = 0;
    for (int i = 0; i < n || carry; ++i) {
        int x = carry;
        if (i < (int)a.size()) x += a[i];
        if (i < (int)b.size()) x += b[i];
        carry = x / 10;
        res.push_back(x % 10);
    }
    while (res.size() > 1 && res.back() == 0)
        res.pop_back();
    return res;
}

VI sub(const VI &a, const VI &b) {
    // 假設 a >= b
    VI res;
    res.reserve(a.size());
    int carry = 0;
    for (int i = 0; i < (int)a.size(); i++) {
        int x = a[i] - carry - (i < (int)b.size() ? b[i] : 0);
        if (x < 0) x += 10, carry = 1;
        else carry = 0;
        res.push_back(x);
    }
    while (res.size() > 1 && res.back() == 0)
        res.pop_back();
    return res;
}

VI multiply(VI a, VI b) {
    int n = 1;
    while (n < (int)(a.size() + b.size())) n <<= 1;
    a.resize(n);
    b.resize(n);

    ntt(a, false);
    ntt(b, false);
    for (int i = 0; i < n; i++) {
        a[i] = (int)((int64_t)a[i] * b[i] % MOD);
    }
    ntt(a, true);

    VI res(n);
    int64_t carry = 0;
    for (int i = 0; i < n; i++) {
        carry += a[i];
        res[i] = carry % 10;
        carry /= 10;
    }
    while (carry > 0) {
        res.push_back(carry % 10);
        carry /= 10;
    }
    while (res.size() > 1 && res.back() == 0)
        res.pop_back();
    return res;
}

void print(const VI &v) {
    for (int i = (int)v.size() - 1; i >= 0; i--)
        cout << v[i];
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string A, B, op;
    cin >> A >> op >> B;

    // 小數字快速計算,避免使用大數演算法
    if (A.size() <= 9 && B.size() <= 9) {
        long long x = stoll(A), y = stoll(B);
        if (op == "+") cout << x + y << '\n';
        else if (op == "-") cout << x - y << '\n';
        else if (op == "*") cout << x * y << '\n';
        return 0;
    }

    VI a = parse(A), b = parse(B);

    if (op == "+") {
        print(add(a, b));
    } else if (op == "-") {
        if (A == B) {
            cout << 0 << '\n';
        } else {
            print(sub(a, b)); // 假設 A >= B
        }
    } else if (op == "*") {
        print(multiply(a, b));
    }

    return 0;
}

 

AC (0.6s, 43.4MB)