提交记录 5776


用户 题目 状态 得分 用时 内存 语言 代码长度
EntropyIncreaser 1004. 【模板题】高精度乘法 Accepted 100 372.617 ms 27148 KB C++ 3.85 KB
提交时间 评测时间
2018-09-02 21:15:25 2020-08-01 00:34:10
#include <cstdio>
#include <cstring>

#include <algorithm>
#include <complex>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;
typedef complex<double> cd;

const int BASE = 5, MOD = 100000;

namespace DivHelper {}

class UnsignedDigit {
private:
	vector<int> digits;

public:
	UnsignedDigit() : digits(1) {}

	UnsignedDigit(const vector<int>& digits);

	UnsignedDigit(ll x);

	UnsignedDigit(char*);

	void print() const;

	bool operator<(const UnsignedDigit& rhs) const;

	UnsignedDigit operator+(const UnsignedDigit& rhs) const;
	UnsignedDigit operator-(const UnsignedDigit& rhs) const;
	UnsignedDigit operator*(const UnsignedDigit& rhs) const;

	UnsignedDigit operator/(int v) const;

	UnsignedDigit move(int k) const;

private:
	void trim();
};

class UnsignedDecimal {};

class Int {};

class Decimal {};

namespace ConvHelper {

	void fft(cd* a, int lgn, int d) {
		int n = 1 << lgn;
		{
			static vector<int> brev;
			if (n != brev.size()) {
				brev.resize(n);
				for (int i = 0; i < n; ++i)
					brev[i] = (brev[i >> 1] >> 1) | ((i & 1) << (lgn - 1));
			}
			for (int i = 0; i < n; ++i)
				if (brev[i] < i)
					swap(a[brev[i]], a[i]);
		}
		for (int t = 1; t < n; t <<= 1) {
			for (int i = 0; i < n; i += t << 1) {
				cd* p = a + i;
				for (int j = 0; j < t; ++j) {
					cd w(cos(M_PI * j / t), sin(M_PI * j * d / t));
					cd x = p[j + t] * w;
					p[j + t] = p[j] - x;
					p[j] += x;
				}
			}
		}
		if (d == -1) {
			for (int i = 0; i < n; ++i)
				a[i] /= n;
		}
	}

	vector<ll> conv(const vector<int>& a, const vector<int>& b) {
		int n = a.size() - 1, m = b.size() - 1;
		if (n < 100 / (m + 1) || n < 3 || m < 3) {
			vector<ll> ret(n + m + 1);
			for (int i = 0; i <= n; ++i)
				for (int j = 0; j <= m; ++j)
					ret[i + j] += a[i] * (ll)b[j];
			return ret;
		}
		int lgn = 0;
		while ((1 << lgn) <= n + m)
			++lgn;
		vector<cd> ta(a.begin(), a.end()), tb(b.begin(), b.end());
		ta.resize(1 << lgn);
		tb.resize(1 << lgn);
		fft(ta.begin().base(), lgn, 1);
		fft(tb.begin().base(), lgn, 1);
		for (int i = 0; i < (1 << lgn); ++i)
			ta[i] *= tb[i];
		fft(ta.begin().base(), lgn, -1);
		vector<ll> ret(n + m + 1);
		for (int i = 0; i <= n + m; ++i)
			ret[i] = ta[i].real() + 0.5;
		return ret;
	}

}

UnsignedDigit::UnsignedDigit(ll x) {
	while (x) {
		digits.push_back(x % MOD);
		x /= MOD;
	}
	if (digits.empty())
		digits.push_back(0);
}

UnsignedDigit UnsignedDigit::operator*(const UnsignedDigit& rhs) const {
	vector<ll> tmp = ConvHelper::conv(digits, rhs.digits);
	for (int i = 0; i + 1 < tmp.size(); ++i) {
		tmp[i + 1] += tmp[i] / MOD;
		tmp[i] %= MOD;
	}
	while (tmp.back() >= MOD) {
		ll remain = tmp.back() / MOD;
		tmp.back() %= MOD;
		tmp.push_back(remain);
	}
	return vector<int>(tmp.begin(), tmp.end());
}

UnsignedDigit::UnsignedDigit(const vector<int>& digits) : digits(digits) {
	if (this->digits.empty())
		this->digits.resize(1);
	trim();
}

void UnsignedDigit::trim() {
	while (digits.size() > 1 && digits.back() == 0)
		digits.pop_back();
}

void UnsignedDigit::print() const {
	printf("%d", digits.back());
	for (int i = (int)digits.size() - 2; i >= 0; --i) {
		printf("%05d", digits[i]);
	}
}

UnsignedDigit::UnsignedDigit(char* s) {
	int n = strlen(s);
	reverse(s, s + n);
	digits.resize((n + BASE - 1) / BASE);
	int cur = 1;
	for (int i = 0; i < n; ++i) {
		if (i % BASE == 0)
			cur = 1;
		digits[i / BASE] += cur * (s[i] - '0');
		cur *= 10;
	}
	trim();
}

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>

#include <algorithm>
#include <functional>
#include <set>
#include <map>
#include <vector>
#include <limits>
#include <numeric>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

char s[1000010];

int main() {

	scanf("%s", s);
	UnsignedDigit a(s);
	scanf("%s", s);
	UnsignedDigit b(s);
	(a * b).print();

	return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #1372.617 ms26 MB + 524 KBAcceptedScore: 100


Judge Duck Online | 评测鸭在线
Server Time: 2020-10-23 14:04:19 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用