[C++] Templates

本文为各种到处搞来的 C++ 模板

快读

template <class T>
void read(T &n)
{
    n = 0;
    bool f(false);
    char ch;
    do
        if ((ch = getchar()) == '-')
            f = true;
    while (ch < '0' || ch > '9');
    while ('0' <= ch && ch <= '9')
    {
        n = (n << 1) + (n << 3) + ch - '0';
        ch = getchar();
    }
    if (f)
        n = ~(n - 1);
}

快写

template <class T>
void write(T n)
{
    if (n < 0)
    {
        n = ~(n - 1);
        putchar('-');
    }
    if (n > 9)
        write(n / 10);
    putchar(n % 10 + '0');
}

最大公因数

辗转相除法

template <class T>
inline T gcd(T a, T b)
{
    if (a % b == 0)
        return a;
    return gcd(b, a % b)
}

位运算

template <class T>
inline T gcd(T a, T b)
{
    while (a ^= b ^= a ^= b %= a)
        ;
    return b;
}

最小公倍数

template <class T>
inline T lcm(T a, T b)
{
    return T(a * b / gcd(a, b));
}

快速幂

template <class T>
T pow(T a, T b, T p)
{
    T ans = 1;
    while (b)
    {
        if (b & 1)
            ans = ans * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return ans;
}

高精度

struct Big : vector<int>
{
    Big(int n = 0)
    {
        push_back(n);
        check();
    }
    Big &check()
    {
        while (!empty() && !back())
            pop_back();
        if (empty())
            return *this;
        for (int i = 1; i < size(); ++i)
        {
            (*this)[i] += (*this)[i - 1] / 10;
            (*this)[i - 1] %= 10;
        }
        while (back() >= 10)
        {
            push_back(back() / 10);
            (*this)[size() - 2] %= 10;
        }
        return *this;
    }
};
istream &operator>>(istream &is, Big &n)
{
    string s;
    is >> s;
    n.clear();
    for (int i = s.size() - 1; i >= 0; --i)
        n.push_back(s[i] - '0');
    return is;
}
ostream &operator<<(ostream &os, const Big &n)
{
    if (n.empty())
        os << 0;
    for (int i = n.size() - 1; i >= 0; --i)
        os << n[i];
    return os;
}
bool operator!=(const Big &a, const Big &b)
{
    if (a.size() != b.size())
        return 1;
    for (int i = a.size() - 1; i >= 0; --i)
        if (a[i] != b[i])
            return 1;
    return 0;
}
bool operator==(const Big &a, const Big &b)
{
    return !(a != b);
}
bool operator<(const Big &a, const Big &b)
{
    if (a.size() != b.size())
        return a.size() < b.size();
    for (int i = a.size() - 1; i >= 0; --i)
        if (a[i] != b[i])
            return a[i] < b[i];
    return 0;
}
bool operator>(const Big &a, const Big &b)
{
    return b < a;
}
bool operator<=(const Big &a, const Big &b)
{
    return !(a > b);
}
bool operator>=(const Big &a, const Big &b)
{
    return !(a < b);
}
Big &operator+=(Big &a, const Big &b)
{
    if (a.size() < b.size())
        a.resize(b.size());
    for (int i = 0; i != b.size(); ++i)
        a[i] += b[i];
    return a.check();
}
Big operator+(Big a, const Big &b)
{
    return a += b;
}
Big &operator-=(Big &a, Big b)
{
    if (a < b)
        swap(a, b);
    for (int i = 0; i != b.size(); a[i] -= b[i], ++i)
        if (a[i] < b[i])
        {
            int j = i + 1;
            while (!a[j])
                ++j;
            while (j > i)
            {
                --a[j];
                a[--j] += 10;
            }
        }
    return a.check();
}
Big operator-(Big a, const Big &b)
{
    return a -= b;
}
Big operator*(const Big &a, const Big &b)
{
    Big n;
    n.assign(a.size() + b.size() - 1, 0);
    for (int i = 0; i != a.size(); ++i)
        for (int j = 0; j != b.size(); ++j)
            n[i + j] += a[i] * b[j];
    return n.check();
}
Big &operator*=(Big &a, const Big &b)
{
    return a = a * b;
}
Big divmod(Big &a, const Big &b)
{
    Big ans;
    for (int t = a.size() - b.size(); a >= b; --t)
    {
        Big d;
        d.assign(t + 1, 0);
        d.back() = 1;
        Big c = b * d;
        while (a >= c)
        {
            a -= c;
            ans += d;
        }
    }
    return ans;
}
Big operator/(Big a, const Big &b)
{
    return divmod(a, b);
}
Big &operator/=(Big &a, const Big &b)
{
    return a = a / b;
}
Big &operator%=(Big &a, const Big &b)
{
    divmod(a, b);
    return a;
}
Big operator%(Big a, const Big &b)
{
    return a %= b;
}
Big pow(Big a, int b)
{
    Big ans = 1;
    while (b)
    {
        if (b & 1)
            ans = ans * a;
        a = a * a;
        b >>= 1;
    }
    return ans;
}