#include <bits/stdc++.h>
#ifndef __DEBUG_LIB
#define __DEBUG_LIB
bool isdebug = false;
#define change(x) isdebug = x
#define Debugc if(isdebug) cout
#define Debug if(isdebug)
#endif
using namespace std;
#define LL long long
#define Pii pair<int, int>
#define ULL unsigned long long
//#define ONLINE_JUDGE luogu
namespace gdb7
{
class Bigint {
private:
static constexpr int indbase = 18;
static const LL base = pow(10, indbase);
vector<LL> v;
public:
void read() {
string str;
cin >> str;
while (str.size() % indbase != 0) {
str = "0" + str;
}
for (int i = str.size() - indbase; i >= 0; i -= indbase) {
v.push_back(stoll(str.substr(i, indbase)));
}
}
void write() const {
for (int i = v.size() - 1; i >= 0; --i) {
if (i == v.size() - 1) {
cout << v[i];
} else {
cout << setfill('0') << setw(indbase) << v[i];
}
}
cout << '\n';
}
const Bigint operator+(const Bigint &rhs) const {
Bigint ans;
for (int i = 0; i <= max(rhs.v.size(), v.size()); ++i) {
ans.v.push_back(0);
}
for (int i = 0; i < min(rhs.v.size(), v.size()); ++i) {
ans.v[i] += rhs.v[i] + v[i];
ans.v[i + 1] += ans.v[i] / base;
ans.v[i] %= base;
}
for (int i = min(rhs.v.size(), v.size()); i < max(rhs.v.size(), v.size()); ++i) {
ans.v[i] += (rhs.v.size() > v.size() ? rhs.v : v)[i];
ans.v[i + 1] += ans.v[i] / base;
ans.v[i] %= base;
}
while (!ans.v[ans.v.size() - 1] && ans.v.size() > 1) {
ans.v.pop_back();
}
return ans;
}
const Bigint operator-(const Bigint &rhs) const {
Bigint ans;
for (int i = 0; i < v.size(); ++i) {
ans.v.push_back(0);
}
for (int i = 0; i < rhs.v.size(); ++i) {
ans.v[i] += v[i] - rhs.v[i];
if (ans.v[i] < 0) {
--ans.v[i + 1];
ans.v[i] += base;
}
}
for (int i = rhs.v.size(); i < v.size(); ++i) {
ans.v[i] += v[i];
}
while (!ans.v[ans.v.size() - 1] && ans.v.size() > 1) {
ans.v.pop_back();
}
return ans;
}
const Bigint operator*(const Bigint &rhs) const {
Bigint ans;
if (v.size() <= 100 && rhs.v.size() <= 100) {
for (int i = 0; i < v.size() + rhs.v.size(); ++i) {
ans.v.push_back(0);
}
for (int i = 0; i < v.size(); ++i) {
for (int j = 0; j < rhs.v.size(); ++j) {
// cout << i << " " << j << endl;
ans.v[i + j] += v[i] * rhs.v[j];
ans.v[i + j + 1] += ans.v[i + j] / base;
ans.v[i + j] %= base;
}
}
while (!ans.v[ans.v.size() - 1] && ans.v.size() > 1) {
ans.v.pop_back();
}
} else {
Bigint a, b, c, d;
const int cut = (max(rhs.v.size(), v.size()) >> 1);
for (int i = cut; i < v.size(); ++i) {
a.v.push_back(v[i]);
}
for (int i = 0; i < cut; ++i) {
b.v.push_back(v[i]);
}
for (int i = cut; i < rhs.v.size(); ++i) {
c.v.push_back(rhs.v[i]);
}
for (int i = 0; i < cut; ++i) {
d.v.push_back(rhs.v[i]);
}
Bigint ac = a * c, bd = b * d;
Bigint e = (a + b) * (c + d) - ac - bd;
ans.v.insert(ans.v.end(), ac.v.begin(), ac.v.end()); /*****/
ans.v.insert(ans.v.end(), e.v.begin(), e.v.end()); /*****/
ans.v.insert(ans.v.end(), bd.v.begin(), bd.v.end()); /*****/
}
return ans;
}
};
signed main() {
// freopen("C:/Users/42175/OneDrive/Desktop/Luogu Problem Data/P1919_1.in", "r", stdin);
// freopen("myout.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0);
Bigint a, b;
a.read();
b.read();
Bigint c = a * b;
c.write();
return 0;
}
};
signed main()
{
return gdb7::main();
}
该代码在提交时会 TLE,咱先不管。
将第一个测试点下载下来后,测试发现 WA,疑似标记 /*****/
的地方有问题。
因为公式为 Ans=ACx2+(AD+BC)x+BD,但这里写的是压位高精(其实还要指令集优化,否则如上文,会 TLE),无法直接在数字的末尾插入 0
,所以只能试试直接将三个数拼起来,但这就会 WA,有没有办法替代。