提交记录 5896


用户 题目 状态 得分 用时 内存 语言 代码长度
EntropyIncreaser 1005a. 【模板题】高精度除法 Accepted 100 4.263 ms 256 KB C++ 7.64 KB
提交时间 评测时间
2018-09-06 11:15:51 2020-08-01 00:35:56
#include <cstdio>
#include <cstring>

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

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

using namespace std;

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

const int BASE = 5, MOD = 100000, LGM = 17;
const double PI = 3.1415926535897932384626;

class UnsignedDigit;

namespace DivHelper { UnsignedDigit quasiInv(const UnsignedDigit& v); }

class UnsignedDigit {
private:
	vector<int> digits;

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

	UnsignedDigit(const vector<int>& digits);

	UnsignedDigit(ll x);

	UnsignedDigit(char* str);

	void print() const;

	bool operator<(const UnsignedDigit& rhs) const;
	bool operator<=(const UnsignedDigit& rhs) 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/(UnsignedDigit rhs) const;

	UnsignedDigit operator/(int v) const;

	UnsignedDigit move(int k) const;

	friend UnsignedDigit DivHelper::quasiInv(const UnsignedDigit& v);
	
	friend void swap(UnsignedDigit& lhs, UnsignedDigit& rhs) { swap(lhs.digits, rhs.digits); }

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(PI * j / t), sin(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;
	}

}

namespace DivHelper {

	UnsignedDigit quasiInv(const UnsignedDigit& v) {
		if (v.digits.size() == 1) {
			UnsignedDigit tmp;
			tmp.digits.resize(3);
			tmp.digits[2] = 1;
			return tmp / v.digits[0];
		}
		if (v.digits.size() == 2) {
			UnsignedDigit sum = 0LL, go = 1;
			vector<int> tmp(4);
			go = go.move(4);
			vector<UnsignedDigit> db(LGM);
			db[0] = v;
			for (int i = 1; i < LGM; ++i)
				db[i] = db[i - 1] + db[i - 1];
			for (int i = 3; i >= 0; --i) {
				for (int k = LGM - 1; k >= 0; --k)
					if (sum + db[k].move(i) <= go) {
						sum = sum + db[k].move(i);
						tmp[i] |= 1 << k;
					}
			}
			return tmp;
		}
		int n = v.digits.size(), k = (n + 2) / 2;
		UnsignedDigit tmp = quasiInv(vector<int>(v.digits.end().base() - k, v.digits.end().base()));
		return (UnsignedDigit(2) * tmp).move(n - k) - (v * tmp * tmp).move(-2 * k);
	}

}

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

UnsignedDigit UnsignedDigit::move(int k) const {
	if (k == 0)
		return *this;
	if (k < 0) {
		if (-k >= digits.size())
			return UnsignedDigit();
		return vector<int>(digits.begin().base() + (-k), digits.end().base());
	}
	if (digits.size() == 1 && digits[0] == 0)
		return UnsignedDigit();
	UnsignedDigit ret;
	ret.digits.resize(k, 0);
	ret.digits.insert(ret.digits.end(), digits.begin(), digits.end());
	return ret;
}

bool UnsignedDigit::operator<(const UnsignedDigit& rhs) const {
	int n = digits.size(), m = rhs.digits.size();
	if (n != m)
		return n < m;
	for (int i = n - 1; i >= 0; --i)
		if (digits[i] != rhs.digits[i])
			return digits[i] < rhs.digits[i];
	return false;
}

bool UnsignedDigit::operator<=(const UnsignedDigit& rhs) const {
	int n = digits.size(), m = rhs.digits.size();
	if (n != m)
		return n < m;
	for (int i = n - 1; i >= 0; --i)
		if (digits[i] != rhs.digits[i])
			return digits[i] < rhs.digits[i];
	return true;
}

bool UnsignedDigit::operator==(const UnsignedDigit& rhs) const {
	int n = digits.size(), m = rhs.digits.size();
	if (n != m)
		return false;
	return memcmp(digits.begin().base(), rhs.digits.begin().base(), n) == 0;
}

UnsignedDigit UnsignedDigit::operator+(const UnsignedDigit& rhs) const {
	int n = digits.size(), m = rhs.digits.size();
	vector<int> tmp = digits;
	if (m > n) {
		tmp.resize(m + 1);
		for (int i = 0; i < m; ++i)
			if ((tmp[i] += rhs.digits[i]) >= MOD) {
				tmp[i] -= MOD;
				++tmp[i + 1];
			}
	} else {
		tmp.resize(n + 1);
		for (int i = 0; i < m; ++i)
			if ((tmp[i] += rhs.digits[i]) >= MOD) {
				tmp[i] -= MOD;
				++tmp[i + 1];
			}
		for (int i = m; i < n; ++i)
			if (tmp[i] == MOD) {
				tmp[i] = 0;
				++tmp[i + 1];
			}
	}
	return tmp;
}

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::operator/(UnsignedDigit rhs) const {
	int m = digits.size(), n = rhs.digits.size(), t = 0;
	if (m < n)
		return 0LL;
	if (m > n * 2)
		t = m - 2 * n;
	rhs = DivHelper::quasiInv(rhs.move(t));
	UnsignedDigit ret = move(t) * rhs;
	return ret.move(-2 * (n + t));
}

UnsignedDigit UnsignedDigit::operator/(int k) const {
	UnsignedDigit ret;
	int n = digits.size();
	ret.digits.resize(n);
	ll r = 0;
	for (int i = n - 1; i >= 0; --i) {
		r = r * MOD + digits[i];
		ret.digits[i] = r / k;
		r %= k;
	}
	ret.trim();
	return ret;
}

UnsignedDigit UnsignedDigit::operator-(const UnsignedDigit& rhs) const {
	UnsignedDigit ret(*this);
	int n = rhs.digits.size();
	for (int i = 0; i < n; ++i)
		if ((ret.digits[i] -= rhs.digits[i]) < 0) {
			ret.digits[i] += MOD;
			--ret.digits[i + 1];
		}
	ret.trim();
	return ret;
}

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());
	int j = 0;
	for (int i = (int)digits.size() - 2; i >= 0; --i) {
		printf("%05d", digits[i]);
		++j;
	}
}

UnsignedDigit::UnsignedDigit(char* str) {
	int n = strlen(str);
	reverse(str, str + 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 * (str[i] - '0');
		cur *= 10;
	}
	trim();
}

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

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


using namespace std;

typedef long long ll;
typedef unsigned long long ull;

char s[10010];

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 #14.263 ms256 KBAcceptedScore: 100


Judge Duck Online | 评测鸭在线
Server Time: 2024-10-05 12:29:48 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用