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