|
|
| （未显示同一用户的2个中间版本） |
| 第1行： |
第1行： |
| <syntaxhighlight lang="cpp" inline> </syntaxhighlight>
| | #REDIRECT [[05-算法模板/04-高精度]] |
| | | [[Category:三三文档]] |
| ==封装好的结构体==
| |
| | |
| 实现的内容：
| |
| | |
| * <syntaxhighlight lang="cpp" inline>BigIntTiny a;</syntaxhighlight>：定义了一个大整数变量 <syntaxhighlight lang="cpp" inline>a</syntaxhighlight>，会自动初始化为 $0$
| |
| * <syntaxhighlight lang="cpp" inline>BigIntTiny a = 33;</syntaxhighlight>：通过一个 <syntaxhighlight lang="cpp" inline>int</syntaxhighlight> 类型的值初始化。
| |
| * <syntaxhighlight lang="cpp" inline>BigIntTiny a = s;</syntaxhighlight>：通过一个 <syntaxhighlight lang="cpp" inline>string s;</syntaxhighlight> 来初始化。
| |
| * <syntaxhighlight lang="cpp" inline>a.get_pos(pos)</syntaxhighlight>：获取第 <syntaxhighlight lang="cpp" inline>pos</syntaxhighlight> 位的数位内容
| |
| * <syntaxhighlight lang="cpp" inline>a.to_str()</syntaxhighlight>：得到对应的字符串，一般用来输出
| |
| * <syntaxhighlight lang="cpp" inline>a = -a;</syntaxhighlight>：取反
| |
| * <syntaxhighlight lang="cpp" inline>a < b</syntaxhighlight>、<syntaxhighlight lang="cpp" inline>a == b</syntaxhighlight>、<syntaxhighlight lang="cpp" inline>...</syntaxhighlight>：比较大小
| |
| * <syntaxhighlight lang="cpp" inline>a + b</syntaxhighlight>：高精度加法，允许（<syntaxhighlight lang="cpp" inline>a += b;</syntaxhighlight>）
| |
| * <syntaxhighlight lang="cpp" inline>a - b</syntaxhighlight>：高精度减法
| |
| * <syntaxhighlight lang="cpp" inline>a * b</syntaxhighlight>：高精度乘法
| |
| * <syntaxhighlight lang="cpp" inline>a / b</syntaxhighlight>：高精度除法
| |
| * <syntaxhighlight lang="cpp" inline>a % b</syntaxhighlight>：高精度取模
| |
| | |
| 实际上因为定义了 <syntaxhighlight lang="cpp" inline>int</syntaxhighlight> 对高精度的转换，所以加减乘除都能直接高精对低精运算。
| |
| | |
| <syntaxhighlight lang="cpp" line>
| |
| struct BigIntTiny
| |
| {
| |
| int sign;
| |
| std::vector<int> v;
| |
| | |
| BigIntTiny() : sign(1) {}
| |
| BigIntTiny(const std::string &s) { *this = s; }
| |
| BigIntTiny(int v)
| |
| {
| |
| char buf[21];
| |
| sprintf(buf, "%d", v);
| |
| *this = buf;
| |
| }
| |
| void zip(int unzip)
| |
| {
| |
| if (unzip == 0)
| |
| {
| |
| for (int i = 0; i < (int)v.size(); i++)
| |
| v[i] = get_pos(i * 4) + get_pos(i * 4 + 1) * 10 + get_pos(i * 4 + 2) * 100 + get_pos(i * 4 + 3) * 1000;
| |
| }
| |
| else
| |
| for (int i = (v.resize(v.size() * 4), (int)v.size() - 1), a; i >= 0; i--)
| |
| a = (i % 4 >= 2) ? v[i / 4] / 100 : v[i / 4] % 100, v[i] = (i & 1) ? a / 10 : a % 10;
| |
| setsign(1, 1);
| |
| }
| |
| int get_pos(unsigned pos) const { return pos >= v.size() ? 0 : v[pos]; }
| |
| BigIntTiny &setsign(int newsign, int rev)
| |
| {
| |
| for (int i = (int)v.size() - 1; i > 0 && v[i] == 0; i--)
| |
| v.erase(v.begin() + i);
| |
| sign = (v.size() == 0 || (v.size() == 1 && v[0] == 0)) ? 1 : (rev ? newsign * sign : newsign);
| |
| return *this;
| |
| }
| |
| std::string to_str() const
| |
| {
| |
| BigIntTiny b = *this;
| |
| std::string s;
| |
| for (int i = (b.zip(1), 0); i < (int)b.v.size(); ++i)
| |
| s += char(*(b.v.rbegin() + i) + '0');
| |
| return (sign < 0 ? "-" : "") + (s.empty() ? std::string("0") : s);
| |
| }
| |
| bool absless(const BigIntTiny &b) const
| |
| {
| |
| if (v.size() != b.v.size())
| |
| return v.size() < b.v.size();
| |
| for (int i = (int)v.size() - 1; i >= 0; i--)
| |
| if (v[i] != b.v[i])
| |
| return v[i] < b.v[i];
| |
| return false;
| |
| }
| |
| BigIntTiny operator-() const
| |
| {
| |
| BigIntTiny c = *this;
| |
| c.sign = (v.size() > 1 || v[0]) ? -c.sign : 1;
| |
| return c;
| |
| }
| |
| BigIntTiny &operator=(const std::string &s)
| |
| {
| |
| if (s[0] == '-')
| |
| *this = s.substr(1);
| |
| else
| |
| {
| |
| for (int i = (v.clear(), 0); i < (int)s.size(); ++i)
| |
| v.push_back(*(s.rbegin() + i) - '0');
| |
| zip(0);
| |
| }
| |
| return setsign(s[0] == '-' ? -1 : 1, sign = 1);
| |
| }
| |
| bool operator<(const BigIntTiny &b) const
| |
| {
| |
| return sign != b.sign ? sign < b.sign : (sign == 1 ? absless(b) : b.absless(*this));
| |
| }
| |
| bool operator==(const BigIntTiny &b) const { return v == b.v && sign == b.sign; }
| |
| BigIntTiny &operator+=(const BigIntTiny &b)
| |
| {
| |
| if (sign != b.sign)
| |
| return *this = (*this) - -b;
| |
| v.resize(std::max(v.size(), b.v.size()) + 1);
| |
| for (int i = 0, carry = 0; i < (int)b.v.size() || carry; i++)
| |
| {
| |
| carry += v[i] + b.get_pos(i);
| |
| v[i] = carry % 10000, carry /= 10000;
| |
| }
| |
| return setsign(sign, 0);
| |
| }
| |
| BigIntTiny operator+(const BigIntTiny &b) const
| |
| {
| |
| BigIntTiny c = *this;
| |
| return c += b;
| |
| }
| |
| void add_mul(const BigIntTiny &b, int mul)
| |
| {
| |
| v.resize(std::max(v.size(), b.v.size()) + 2);
| |
| for (int i = 0, carry = 0; i < (int)b.v.size() || carry; i++)
| |
| {
| |
| carry += v[i] + b.get_pos(i) * mul;
| |
| v[i] = carry % 10000, carry /= 10000;
| |
| }
| |
| }
| |
| BigIntTiny operator-(const BigIntTiny &b) const
| |
| {
| |
| if (sign != b.sign)
| |
| return (*this) + -b;
| |
| if (absless(b))
| |
| return -(b - *this);
| |
| BigIntTiny c;
| |
| for (int i = 0, borrow = 0; i < (int)v.size(); i++)
| |
| {
| |
| borrow += v[i] - b.get_pos(i);
| |
| c.v.push_back(borrow);
| |
| c.v.back() -= 10000 * (borrow >>= 31);
| |
| }
| |
| return c.setsign(sign, 0);
| |
| }
| |
| BigIntTiny operator*(const BigIntTiny &b) const
| |
| {
| |
| if (b < *this)
| |
| return b * *this;
| |
| BigIntTiny c, d = b;
| |
| for (int i = 0; i < (int)v.size(); i++, d.v.insert(d.v.begin(), 0))
| |
| c.add_mul(d, v[i]);
| |
| return c.setsign(sign * b.sign, 0);
| |
| }
| |
| BigIntTiny operator/(const BigIntTiny &b) const
| |
| {
| |
| BigIntTiny c, d;
| |
| d.v.resize(v.size());
| |
| double db = 1.0 / (b.v.back() + (b.get_pos((unsigned)b.v.size() - 2) / 1e4) +
| |
| (b.get_pos((unsigned)b.v.size() - 3) + 1) / 1e8);
| |
| for (int i = (int)v.size() - 1; i >= 0; i--)
| |
| {
| |
| c.v.insert(c.v.begin(), v[i]);
| |
| int m = (int)((c.get_pos((int)b.v.size()) * 10000 + c.get_pos((int)b.v.size() - 1)) * db);
| |
| c = c - b * m, d.v[i] += m;
| |
| while (!(c < b))
| |
| c = c - b, d.v[i] += 1;
| |
| }
| |
| return d.setsign(sign * b.sign, 0);
| |
| }
| |
| BigIntTiny operator%(const BigIntTiny &b) const { return *this - *this / b * b; }
| |
| bool operator>(const BigIntTiny &b) const { return b < *this; }
| |
| bool operator<=(const BigIntTiny &b) const { return !(b < *this); }
| |
| bool operator>=(const BigIntTiny &b) const { return !(*this < b); }
| |
| bool operator!=(const BigIntTiny &b) const { return !(*this == b); }
| |
| };
| |
| </syntaxhighlight>
| |
| | |
| ==例子==
| |
| | |
| ===阶乘和===
| |
| | |
| <syntaxhighlight lang="cpp" line>
| |
| int main(){
| |
| int n;
| |
| cin >> n;
| |
| BigIntTiny sum = 0;
| |
| BigIntTiny now = 1;
| |
| for(int i = 1; i <= n; i++)
| |
| {
| |
| now = now * i;
| |
| sum += now;
| |
| }
| |
| cout << sum.to_str();
| |
| return 0;
| |
| }
| |
| </syntaxhighlight>
| |
| | |
| ===高精度加法===
| |
| | |
| 一种写法
| |
| | |
| <syntaxhighlight lang="cpp" line>
| |
| string t;
| |
| BigIntTiny a, b;
| |
| int main(){
| |
| cin >> t; a = t;
| |
| cin >> t; b = t;
| |
| cout << (a + b).to_str();
| |
| return 0;
| |
| }
| |
| </syntaxhighlight>
| |
| | |
| 另一种写法
| |
| | |
| <syntaxhighlight lang="cpp" line>
| |
| string a, b;
| |
| int main(){
| |
| cin >> a >> b;
| |
| cout << ((BigIntTiny)a + (BigIntTiny)b).to_str();
| |
| return 0;
| |
| }
| |
| </syntaxhighlight>
| |
| | |
| [[Category:代码模板]] | |