Submission #49973893

---

Source Code Expand

/**
 *  @the_hyp0cr1t3
 *  03.02.2024 18:49
**/
#include <bits/stdc++.h>

#if __cplusplus < 202002L
namespace std {
    template <typename T>
    constexpr int ssize(const T &s) { return s.size(); }
}
#endif

// commonly used:
//  decimal <10, 9, '0'>
//  alphabet <26, 6, 'a'>
//  binary  <2, 30, '0'>
template <int base = 10, int grpsz = 9, char base_char = '0'>
struct bigint {
    static constexpr auto t = []() {
        std::array<int, grpsz + 1> p{1};
        int n = 0, m = 0;
        for (int i = 1; i <= grpsz; ++i) {
            p[i] = p[i - 1] * base;
            if (p[i] <= 1000000) n = i;
        }
        m = p.back();
        return std::make_tuple(m, n, p);
    }();

    // base should not exceed 1e9 (overflow)
    static constexpr int _mod = std::get<0>(t);
    static constexpr int reduced_grpsz = std::get<1>(t);
    static constexpr std::array<int, grpsz + 1> pows = std::get<2>(t);
    static constexpr int karatsubaMinimalSize = 50;

    int sign{1};
    std::vector<int> d;

    // ctors
    bigint(int64_t number = 0) {
        sign = number < 0 ? number = -number, -1 : 1;
        while (number > 0)
            d.emplace_back(number % _mod), number /= _mod;
    }
    // _digits = MSB...LSB (not in groups of size grpsz); sign = -1 || 1
    bigint(const std::vector<int>& _digits, int _sign = 1): sign(_sign) {
        d.reserve(std::ssize(_digits) / grpsz + 1);
        for (int i = std::ssize(_digits) - 1, block = 0; i >= 0; i -= grpsz, block = 0) {
            for (int j = std::max(0, i - grpsz + 1); j <= i; j++)
                block = block * base + _digits[j];
            d.emplace_back(block);
        }
        normalize();
    }
    bigint(const std::string& s): bigint(convert_string_to_vector(s), (s[0] == '-' ? -1 : 1)) {}

    // does not handle overflow
    template<typename T, typename = std::enable_if_t<std::is_integral<T>::value>>
    explicit operator T() const {
        T res = 0;
        for (auto& _d: d)
            res = res * _mod + _d;
        return res * sign;
    }

// io
    std::string to_string() const {
        std::string s;
        if (is0()) s += base_char;
        else {
            for (auto res: d)
                for (int j = 0; j < grpsz; j++)
                    s += res % base + base_char, res /= base;
            while (s.size() and s.back() == base_char) s.pop_back();
            if (sign < 0) s += '-';
            std::reverse(s.begin(), s.end());
        }
        return s;
    }

    friend std::istream& operator>>(std::istream& is, bigint& number) {
        std::string s;
        is >> s;
        number = bigint(s);
        return is;
    }
    friend std::ostream& operator<<(std::ostream& os, const bigint& number) {
        return os << number.to_string();
    }

// helpers
    inline bool is0() const noexcept { return !d.size(); }
    inline void normalize() noexcept {
        while (d.size() and !d.back()) d.pop_back();
        if (!d.size()) sign = 1;
    }
    static std::vector<int> convert_string_to_vector(const std::string& s) {
        std::vector<int> v;
        v.reserve(s.size());
        for (auto c: s)
            if (c != '-') v.emplace_back(c - base_char);
        return v;
    }

// compare
    int compare(const bigint& o) const noexcept {
        if (sign != o.sign) return sign == 1 ? 1 : -1;
        if (std::ssize(d) > std::ssize(o.d)) return sign == 1 ? 1 : -1;
        if (std::ssize(d) < std::ssize(o.d)) return sign == 1 ? -1 : 1;
        for (int i = std::ssize(d) - 1; i >= 0; --i) {
            if (d[i] > o.d[i]) return sign == 1 ? 1 : -1;
            if (d[i] < o.d[i]) return sign == 1 ? -1 : 1;
        }
        return 0;
    }

    bool operator< (const bigint& o) const noexcept { return compare(o) < 0; }
    bool operator> (const bigint& o) const noexcept { return compare(o) > 0; }
    bool operator==(const bigint& o) const noexcept { return compare(o) == 0; }
    bool operator<=(const bigint& o) const noexcept { return compare(o) <= 0; }
    bool operator>=(const bigint& o) const noexcept { return compare(o) >= 0; }
    bool operator!=(const bigint& o) const noexcept { return compare(o) != 0; }

// operator overloads
    int operator[](size_t idx) const noexcept { return d[idx]; }
    bigint operator-() const { bigint res = *this; res.sign *= -1; return res; }
    bigint abs() const { bigint res = *this; res.sign *= res.sign; return res; }

    void increment() {
        for (auto& _d: d) { if (++_d < _mod) return; _d = 0; }
        d.emplace_back(1);
    }
    void decrement() {
        if (is0()) { sign = -1; d.emplace_back(1); }
        else { for (auto& _d: d) { if (_d--) return normalize(); _d = _mod - 1; } }
    }

    bigint& operator++() { sign > 0 ? increment() : decrement(); return *this; }
    bigint& operator--() { sign > 0 ? decrement() : increment(); return *this; }
    bigint operator++(int) { bigint res = *this; ++*this; return res; }
    bigint operator--(int) { bigint res = *this; --*this; return res; }

    bigint& operator+=(const int64_t num) {
        if ((sign > 0) != (num > 0)) return *this -= bigint(-num);
        if (num >= _mod) return *this += bigint(num);
        int carry = num;
        for (int pos = 0; pos < std::ssize(d) and carry; pos++) {
            d[pos] += carry;
            carry = d[pos] >= _mod;
            if (carry) d[pos] -= _mod;
        }
        if (carry) d.emplace_back(1);
        return normalize(), *this;
    }

    bigint& operator+=(const bigint& o) {
        if (sign != o.sign) return *this -= -o;
        d.resize(std::max(std::ssize(d), std::ssize(o.d)));
        int carry = 0;
        for (int pos = 0; pos < std::ssize(d); pos++) {
            d[pos] += carry + (pos < std::ssize(o.d) ? o.d[pos] : 0);
            carry = d[pos] >= _mod;
            if (carry) d[pos] -= _mod;
        }
        if (carry) d.emplace_back(1);
        return *this;
    }

    bigint& operator-=(const bigint& o) {
        if (sign != o.sign) return *this += -o;
        if (o.abs() > abs()) return *this = -(o - *this);
        int carry = 0;
        for (int pos = 0; pos < std::ssize(o.d) or carry; pos++) {
            d[pos] -= carry + (pos < std::ssize(o.d) ? o.d[pos] : 0);
            carry = d[pos] < 0;
            if (carry) d[pos] += _mod;
        }
        return normalize(), *this;
    }

    bigint operator+(const bigint& o) const { bigint res = *this; res += o; return res; }
    bigint operator-(const bigint& o) const { bigint res = *this; res -= o; return res; }

    bigint& operator*=(int num) {
        if (num < 0) sign = -sign, num = -num;
        if (num >= _mod) return *this *= bigint(num), *this;
        int64_t rem = 0;
        for (auto& i : d) {
            rem += 1LL * i * num;
            int64_t div = rem / _mod;
            i = rem - div*_mod;
            rem = div;
        }
        if (rem > 0) d.emplace_back(rem);
        return normalize(), *this;
    }

    bigint operator*(int num) const { bigint res = *this; res *= num; return res; }
    bigint operator*=(const bigint& o) { return *this = *this * o; }

    bigint operator*(const bigint &o) const {
        std::vector<int64_t> U = convert_base<int64_t>(d, grpsz, reduced_grpsz);
        std::vector<int64_t> V = convert_base<int64_t>(o.d, grpsz, reduced_grpsz);
        int32_t _sz = std::max(std::ssize(U), std::ssize(V));
        _sz--; _sz |= _sz >> 1; _sz |= _sz >> 2; _sz |= _sz >> 4;
        _sz |= _sz >> 8; _sz |= _sz >> 16; _sz++;
        U.resize(_sz); V.resize(_sz);
        std::vector<int64_t> ret = karatsubaMultiply(U, V, 0, _sz);
        bigint res; res.sign = sign * o.sign;
        res.d.reserve(std::ssize(ret));
        for (int i = 0, carry = 0; i < std::ssize(ret); i++) {
            int64_t cur = ret[i] + carry;
            res.d.emplace_back(cur % pows[reduced_grpsz]);
            carry = cur / pows[reduced_grpsz];
        }
        res.d = convert_base<int>(res.d, reduced_grpsz, grpsz);
        res.normalize();
        return res;
    }

    bigint& operator/=(int num) {
        assert(num && "Divide by zero");
        if (num >= _mod) return *this /= bigint(num);
        if (num < 0) sign = -sign, num = -num;
        int64_t rem = 0;
        for (int j = std::ssize(d) - 1; ~j; j--) {
            (rem *= _mod) += d[j];
            int64_t div = rem / num;
            d[j] = div;
            rem -= div * num;
        }
        return normalize(), *this;
    }

    int operator%(int num) const {
        assert(num && "Divide by zero");
        if (num < 0) num = -num;
        int64_t rem = 0;
        for (int i = std::ssize(d) - 1; i >= 0; i--)
            ((rem *= _mod) += d[i]) %= num;
        return rem * sign;
    }

    bigint operator/(int num) const { bigint res = *this; res /= num; return res; }
    bigint& operator/=(const bigint& o) { return *this = div_mod(o).first; }
    bigint operator/(const bigint& o) const { return div_mod(o).first; }
    bigint& operator%=(const bigint& o) { return *this = div_mod(o).second; }
    bigint operator%(const bigint& o) const { return div_mod(o).second; }
    bigint operator^(const bigint& o) const {   // exponentiate
        bigint res{1}, A = *this, B = o;
        while (!B.is0()) {
            if (B % 2) res *= A;
            B /= 2; A *= A;
        }
        return res;
    }

// Misc.
    template<typename T>
    static std::vector<T> convert_base(const std::vector<int>& v, int from_cnt, int to_cnt) {
        std::vector<T> res; int64_t cur = 0, have = 0;
        for (int i = 0; i < std::ssize(v); i++) {
            cur += 1LL * pows[have] * v[i];
            have += from_cnt;
            while (have >= to_cnt) {
                res.emplace_back(cur % pows[to_cnt]);
                cur /= pows[to_cnt]; have -= to_cnt;
            }
        }
        res.emplace_back(cur);
        while (!res.empty() && !res.back()) res.pop_back();
        return res;
    }

    static inline std::vector<int64_t> karatsubaSum(const std::vector<int64_t>& V, int pos, int len) {
        std::vector<int64_t> res(len);
        for (int i = 0; i < len; i++)
            res[i] = V[i + pos] + V[i + len + pos];
        return res;
    }

    static std::vector<int64_t> karatsubaMultiply(const std::vector<int64_t>& U, const std::vector<int64_t>& V, int pos, int len) {
        std::vector<int64_t> res(len << 1);
        if (len <= karatsubaMinimalSize) {
            for (int i = 0; i < len; i++)
                for (int j = 0; j < len; j++)
                    res[i + j] += U[i + pos] * V[j + pos];
            return res;
        }
        int k = len >> 1;
        std::vector<int64_t> u1v1 = karatsubaMultiply(U, V, pos, k);
        std::vector<int64_t> u2v2 = karatsubaMultiply(U, V, pos+k, k);
        std::vector<int64_t> usum = karatsubaSum(U, pos, k);
        std::vector<int64_t> vsum = karatsubaSum(V, pos, k);
        std::vector<int64_t> usum_vsum = karatsubaMultiply(usum, vsum, 0, k);
        for (int i = 0; i < len; i++) {
            res[i] += u1v1[i];
            res[i + len] += u2v2[i];
            res[i + k] += usum_vsum[i] - u1v1[i] - u2v2[i];
        }
        return res;
    }

    std::pair<bigint, bigint> div_mod(const bigint& o) const {
        assert(!o.is0() && "Divide by zero");
        std::pair<bigint, bigint> res;
        if (std::ssize(o.d) == 1) {
            res = {*this / o.d[0], *this % o.d[0]};
            return res;
        }
        const int norm = _mod / (o.d.back() + 1);
        const bigint a = *this * norm;
        const bigint b = o * norm;
        const int sz_a = std::ssize(a.d);
        const int sz_b = std::ssize(b.d);
        bigint q, r; q.d.resize(sz_a);
        for (int i = sz_a-1; i >= 0; i--) {
            r *= _mod; r += a.d[i];
            int s1 = std::ssize(r.d) <= sz_b ? 0 : r.d[sz_b];
            int s2 = std::ssize(r.d) <= sz_b-1 ? 0 : r.d[sz_b-1];
            int _d = (1LL * _mod * s1 + s2) / b.d.back();
            auto temp = b * _d;
            while (r < temp)
                r += b, --_d;
            r -= temp;
            q.d[i] = _d;
        }
        q.sign = a.sign * b.sign; r.sign = a.sign;
        q.normalize(); res = {std::move(q), r /= norm};
        return res;
    }

    friend bigint gcd(bigint A, bigint B) {
        while (!B.is0()) {
            A %= B;
            std::swap(A, B);
        }
        return A;
    }
};

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int n;
    std::cin >> n;
    std::vector<int> cnt;
    std::vector<bigint<>> a(n), b;
    for (auto &x : a)
        std::cin >> x;

    std::ranges::sort(a);
    for (int i = 0, j = 0; i < n; i = j) {
        for (; j < n and a[i] == a[j]; j++);
        cnt.push_back(j - i);
        b.push_back(a[i]);
    }

    n = b.size();
    auto inf = bigint<>('1' + std::string(1000, '0'));

    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            auto x = b[i] * b[j];
            if (x > inf) break;
            int lo = 0, hi = n - 1;
            while (lo <= hi) {
                auto m = std::midpoint(lo, hi);
                b[m] < x ? lo = m + 1 : hi = m - 1;
            }
            if (lo < n and b[lo] == x)
                ans += cnt[i] * cnt[j] * cnt[lo];
        }
    }

    std::cout << ans << '\n';
}

Submission Info

Judge Result