library

This documentation is automatically generated by online-judge-tools/verification-helper

Project maintained by tko919 Hosted on GitHub Pages — Theme by mattgraham

:warning: Represent A Number As Two Square Sum
(Math/twosquare.hpp)

Depends on

Code

#pragma once
#include "Math/primitive.hpp"
#include "Math/gaussian.hpp"
#include "Math/pollard.hpp"

vector<pair<ll, ll>> RepresentTwoSquare(ll n) {
    auto find = [&](ll p) -> Gauss<ll> {
        assert(p % 4 == 1);
        ll g = 1, x = -1;
        for (;;) {
            g++;
            x = mpow(g, (p - 1) / 4, p);
            if ((__int128_t(x) * x) % p == p - 1)
                break;
        }
        Gauss<ll> a(p, 0), b(x, 1);
        a = gcd(a, b);
        assert(a.norm() == p);
        return a;
    };
    auto subtask = [&](ll p, int e) -> vector<Gauss<ll>> {
        if (p == 2) {
            Gauss<ll> ret(1, 0), b(1, 1);
            rep(_, 0, e) ret *= b;
            return {ret};
        } else if (p % 4 == 1) {
            auto base = find(p);
            vector<Gauss<ll>> pws(e + 1), ret(e + 1);
            pws[0] = Gauss<ll>(1, 0);
            rep(i, 0, e) pws[i + 1] = pws[i] * base;
            rep(i, 0, e + 1) ret[i] = pws[i] * pws[e - i].conj();
            return ret;
        } else {
            if (e & 1)
                return {};
            ll q = 1;
            rep(_, 0, e / 2) q *= p;
            return {Gauss<ll>(q, 0)};
        }
    };

    if (n == 0) {
        return {{0, 0}};
    }
    auto ps = Pollard(n);
    map<ll, int> pe;
    for (auto &p : ps)
        pe[p]++;
    vector<Gauss<ll>> ret;
    ret.push_back(Gauss<ll>(1, 0));
    for (auto &[p, e] : pe) {
        auto add = subtask(p, e);
        vector<Gauss<ll>> nxt;
        for (auto &x : ret) {
            for (auto &y : add) {
                nxt.push_back(x * y);
            }
        }
        swap(ret, nxt);
    }
    vector<pair<ll, ll>> out;
    for (auto x : ret) {
        rep(_, 0, 4) {
            swap(x.x, x.y);
            x.x *= -1;
            if (x.x >= 0 and x.y >= 0) {
                out.push_back({x.x, x.y});
            }
        }
    }
    return out;
}

/**
 * @brief Represent A Number As Two Square Sum
 */
#line 2 "Math/fastdiv.hpp"

struct FastDiv {
    using u64 = uint64_t;
    using u128 = __uint128_t;
    constexpr FastDiv() : m(), s(), x() {}
    constexpr FastDiv(int _m)
        : m(_m), s(__lg(m - 1)), x(((u128(1) << (s + 64)) + m - 1) / m) {}
    constexpr int get() {
        return m;
    }
    constexpr friend u64 operator/(u64 n, const FastDiv &d) {
        return (u128(n) * d.x >> d.s) >> 64;
    }
    constexpr friend int operator%(u64 n, const FastDiv &d) {
        return n - n / d * d.m;
    }
    constexpr pair<u64, int> divmod(u64 n) const {
        u64 q = n / (*this);
        return {q, n - q * m};
    }
    int m, s;
    u64 x;
};

struct FastDiv64 {
    using u64 = uint64_t;
    using u128 = __uint128_t;
    u128 mod, mh, ml;
    explicit FastDiv64(u64 mod = 1) : mod(mod) {
        u128 m = u128(-1) / mod;
        if (m * mod + mod == u128(0))
            ++m;
        mh = m >> 64;
        ml = m & u64(-1);
    }
    u64 umod() const {
        return mod;
    }
    u64 modulo(u128 x) {
        u128 z = (x & u64(-1)) * ml;
        z = (x & u64(-1)) * mh + (x >> 64) * ml + (z >> 64);
        z = (x >> 64) * mh + (z >> 64);
        x -= z * mod;
        return x < mod ? x : x - mod;
    }
    u64 mul(u64 a, u64 b) {
        return modulo(u128(a) * b);
    }
};

/**
 * @brief Fast Division
 */
#line 2 "Math/miller.hpp"

struct m64 {
    using i64 = int64_t;
    using u64 = uint64_t;
    using u128 = __uint128_t;

    static u64 mod;
    static u64 r;
    static u64 n2;

    static u64 get_r() {
        u64 ret = mod;
        rep(_,0,5) ret *= 2 - mod * ret;
        return ret;
    }

    static void set_mod(u64 m) {
        assert(m < (1LL << 62));
        assert((m & 1) == 1);
        mod = m;
        n2 = -u128(m) % m;
        r = get_r();
        assert(r * mod == 1);
    }
    static u64 get_mod() { return mod; }

    u64 a;
    m64() : a(0) {}
    m64(const int64_t &b) : a(reduce((u128(b) + mod) * n2)){};

    static u64 reduce(const u128 &b) {
        return (b + u128(u64(b) * u64(-r)) * mod) >> 64;
    }
    u64 get() const {
        u64 ret = reduce(a);
        return ret >= mod ? ret - mod : ret;
    }
    m64 &operator*=(const m64 &b) {
        a = reduce(u128(a) * b.a);
        return *this;
    }
    m64 operator*(const m64 &b) const { return m64(*this) *= b; }
    bool operator==(const m64 &b) const {
        return (a >= mod ? a - mod : a) == (b.a >= mod ? b.a - mod : b.a);
    }
    bool operator!=(const m64 &b) const {
        return (a >= mod ? a - mod : a) != (b.a >= mod ? b.a - mod : b.a);
    }
    m64 pow(u128 n) const {
        m64 ret(1), mul(*this);
        while (n > 0) {
        if (n & 1) ret *= mul;
        mul *= mul;
        n >>= 1;
        }
        return ret;
    }
};
typename m64::u64 m64::mod, m64::r, m64::n2;

bool Miller(ll n){
    if(n<2 or (n&1)==0)return (n==2);
    m64::set_mod(n);
    ll d=n-1; while((d&1)==0)d>>=1;
    vector<ll> seeds;
    if(n<(1<<30))seeds={2, 7, 61};
    else seeds={2, 325, 9375, 28178, 450775, 9780504};
    for(auto& x:seeds){
        if(n<=x)break;
        ll t=d;
        m64 y=m64(x).pow(t);
        while(t!=n-1 and y!=1 and y!=n-1){
            y*=y;
            t<<=1;
        }
        if(y!=n-1 and (t&1)==0)return 0;
    } return 1;
}

/**
 * @brief Miller-Rabin
 */
#line 2 "Utility/random.hpp"

namespace Random {
mt19937_64 randgen(chrono::steady_clock::now().time_since_epoch().count());
using u64 = unsigned long long;
u64 get() {
    return randgen();
}
template <typename T> T get(T L) { // [0,L]

    return get() % (L + 1);
}
template <typename T> T get(T L, T R) { // [L,R]

    return get(R - L) + L;
}
double uniform() {
    return double(get(1000000000)) / 1000000000;
}
string str(int n) {
    string ret;
    rep(i, 0, n) ret += get('a', 'z');
    return ret;
}
template <typename Iter> void shuffle(Iter first, Iter last) {
    if (first == last)
        return;
    int len = 1;
    for (auto it = first + 1; it != last; it++) {
        len++;
        int j = get(0, len - 1);
        if (j != len - 1)
            iter_swap(it, first + j);
    }
}
template <typename T> vector<T> select(int n, T L, T R) { // [L,R]

    if (n * 2 >= R - L + 1) {
        vector<T> ret(R - L + 1);
        iota(ALL(ret), L);
        shuffle(ALL(ret));
        ret.resize(n);
        return ret;
    } else {
        unordered_set<T> used;
        vector<T> ret;
        while (SZ(used) < n) {
            T x = get(L, R);
            if (!used.count(x)) {
                used.insert(x);
                ret.push_back(x);
            }
        }
        return ret;
    }
}

void relabel(int n, vector<pair<int, int>> &es) {
    shuffle(ALL(es));
    vector<int> ord(n);
    iota(ALL(ord), 0);
    shuffle(ALL(ord));
    for (auto &[u, v] : es)
        u = ord[u], v = ord[v];
}
template <bool directed, bool simple> vector<pair<int, int>> genGraph(int n) {
    vector<pair<int, int>> cand, es;
    rep(u, 0, n) rep(v, 0, n) {
        if (simple and u == v)
            continue;
        if (!directed and u > v)
            continue;
        cand.push_back({u, v});
    }
    int m = get(SZ(cand));
    vector<int> ord;
    if (simple)
        ord = select(m, 0, SZ(cand) - 1);
    else {
        rep(_, 0, m) ord.push_back(get(SZ(cand) - 1));
    }
    for (auto &i : ord)
        es.push_back(cand[i]);
    relabel(n, es);
    return es;
}
vector<pair<int, int>> genTree(int n) {
    vector<pair<int, int>> es;
    rep(i, 1, n) es.push_back({get(i - 1), i});
    relabel(n, es);
    return es;
}
}; // namespace Random


/**
 * @brief Random
 */
#line 4 "Math/pollard.hpp"

vector<ll> Pollard(ll n) {
    if (n <= 1)
        return {};
    if (Miller(n))
        return {n};
    if ((n & 1) == 0) {
        vector<ll> v = Pollard(n >> 1);
        v.push_back(2);
        return v;
    }
    for (ll x = 2, y = 2, d;;) {
        ll c = Random::get(2LL, n - 1);
        do {
            x = (__int128_t(x) * x + c) % n;
            y = (__int128_t(y) * y + c) % n;
            y = (__int128_t(y) * y + c) % n;
            d = __gcd(x - y + n, n);
        } while (d == 1);
        if (d < n) {
            vector<ll> lb = Pollard(d), rb = Pollard(n / d);
            lb.insert(lb.end(), ALL(rb));
            return lb;
        }
    }
}

/**
 * @brief Pollard-Rho
 */
#line 4 "Math/primitive.hpp"

ll mpow(ll a, ll t, ll m) {
    ll res = 1;
    FastDiv64 im(m);
    while (t) {
        if (t & 1)
            res = im.modulo(__int128_t(res) * a);
        a = im.modulo(__int128_t(a) * a);
        t >>= 1;
    }
    return res;
}
ll minv(ll a, ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b;
        swap(a, b);
        u -= t * v;
        swap(u, v);
    }
    u = (u % m + m) % m;
    return u;
}
ll getPrimitiveRoot(ll p) {
    vector<ll> ps = Pollard(p - 1);
    sort(ALL(ps));
    rep(x, 1, inf) {
        for (auto &q : ps) {
            if (mpow(x, (p - 1) / q, p) == 1)
                goto fail;
        }
        return x;
    fail:;
    }
    assert(0);
}
ll extgcd(ll a, ll b, ll &p, ll &q) {
    if (b == 0) {
        p = 1;
        q = 0;
        return a;
    }
    ll d = extgcd(b, a % b, q, p);
    q -= a / b * p;
    return d;
}
pair<ll, ll> crt(const vector<ll> &vs, const vector<ll> &ms) {
    ll V = vs[0], M = ms[0];
    rep(i, 1, vs.size()) {
        ll p, q, v = vs[i], m = ms[i];
        if (M < m)
            swap(M, m), swap(V, v);
        ll d = extgcd(M, m, p, q);
        if ((v - V) % d != 0)
            return {0, -1};
        ll md = m / d, tmp = (v - V) / d % md * p % md;
        V += M * tmp;
        M *= md;
    }
    V = (V % M + M) % M;
    return {V, M};
}
ll ModLog(ll a, ll b, ll p) {
    ll g = 1;
    for (ll t = p; t; t >>= 1)
        g = g * a % p;
    g = __gcd(g, p);
    ll t = 1, c = 0;
    for (; t % g; c++) {
        if (t == b)
            return c;
        t = t * a % p;
    }
    if (b % g)
        return -1;
    t /= g, b /= g;
    ll n = p / g, h = 0, gs = 1;
    for (; h * h < n; h++)
        gs = gs * a % n;
    unordered_map<ll, ll> bs;
    for (ll s = 0, e = b; s < h; bs[e] = ++s)
        e = e * a % n;
    for (ll s = 0, e = t; s < n;) {
        e = e * gs % n, s += h;
        if (bs.count(e)) {
            return c + s - bs[e];
        }
    }
    return -1;
}

ll mod_root(ll k, ll a, ll m) {
    if (a == 0)
        return k ? 0 : -1;
    if (m == 2)
        return a & 1;
    k %= m - 1;
    ll g = gcd(k, m - 1);
    if (mpow(a, (m - 1) / g, m) != 1)
        return -1;
    a = mpow(a, minv(k / g, (m - 1) / g), m);
    FastDiv im(m);

    auto _subroot = [&](ll p, int e, ll a) -> ll { // x^(p^e)==a(mod m)

        ll q = m - 1;
        int s = 0;
        while (q % p == 0) {
            q /= p;
            s++;
        }
        int d = s - e;
        ll pe = mpow(p, e, m),
           res = mpow(a, ((pe - 1) * minv(q, pe) % pe * q + 1) / pe, m), c = 1;
        while (mpow(c, (m - 1) / p, m) == 1)
            c++;
        c = mpow(c, q, m);
        map<ll, ll> mp;
        ll v = 1, block = sqrt(d * p) + 1,
           bs = mpow(c, mpow(p, s - 1, m - 1) * block % (m - 1), m);
        rep(i, 0, block + 1) mp[v] = i, v = v * bs % im;
        ll gs = minv(mpow(c, mpow(p, s - 1, m - 1), m), m);
        rep(i, 0, d) {
            ll err = a * minv(mpow(res, pe, m), m) % im;
            ll pos = mpow(err, mpow(p, d - 1 - i, m - 1), m);
            rep(j, 0, block + 1) {
                if (mp.count(pos)) {
                    res = res *
                          mpow(c,
                               (block * mp[pos] + j) * mpow(p, i, m - 1) %
                                   (m - 1),
                               m) %
                          im;
                    break;
                }
                pos = pos * gs % im;
            }
        }
        return res;
    };

    for (ll d = 2; d * d <= g; d++)
        if (g % d == 0) {
            int sz = 0;
            while (g % d == 0) {
                g /= d;
                sz++;
            }
            a = _subroot(d, sz, a);
        }
    if (g > 1)
        a = _subroot(g, 1, a);
    return a;
}

ull floor_root(ull a, ull k) {
    if (a <= 1 or k == 1)
        return a;
    if (k >= 64)
        return 1;
    if (k == 2)
        return sqrtl(a);
    constexpr ull LIM = -1;
    if (a == LIM)
        a--;
    auto mul = [&](ull &x, const ull &y) {
        if (x <= LIM / y)
            x *= y;
        else
            x = LIM;
    };
    auto pw = [&](ull x, ull t) -> ull {
        ull y = 1;
        while (t) {
            if (t & 1)
                mul(y, x);
            mul(x, x);
            t >>= 1;
        }
        return y;
    };
    ull ret = (k == 3 ? cbrt(a) - 1 : pow(a, nextafter(1 / double(k), 0)));
    while (pw(ret + 1, k) <= a)
        ret++;
    return ret;
}

/**
 * @brief Primitive Function
 */
#line 2 "Math/gaussian.hpp"

template <typename T> struct Gauss {
    T x, y;
    Gauss() {}
    Gauss(T _x, T _y) : x(_x), y(_y) {}
    T norm() const {
        return x * x + y * y;
    }
    Gauss conj() const {
        return Gauss(x, -y);
    }
    Gauss operator-() const {
        return Gauss(-x, -y);
    }
    Gauss pow(ll n) const {
        assert(n >= 0);
        Gauss ret(1), mul(*this);
        while (n) {
            if (n & 1)
                ret *= mul;
            mul *= mul;
            n >>= 1;
        }
        return ret;
    }
    Gauss &operator+=(const Gauss &a) {
        x += a.x, y += a.y;
        return *this;
    }
    Gauss &operator-=(const Gauss &a) {
        x -= a.x, y -= a.y;
        return *this;
    }
    Gauss &operator*=(const Gauss &a) {
        T nx = x * a.x - y * a.y, ny = x * a.y + y * a.x;
        x = nx, y = ny;
        return *this;
    }
    Gauss &operator/=(const Gauss &a) {
        (*this) *= a.conj();
        T n = a.norm();
        x = floor(x + n / 2, n), y = floor(y + n / 2, n);
        return *this;
    }
    Gauss &operator%=(const Gauss &a) {
        (*this) -= (Gauss(*this) / a) * a;
        return *this;
    }
    Gauss operator+(const Gauss &a) const {
        return Gauss(*this) += a;
    }
    Gauss operator-(const Gauss &a) const {
        return Gauss(*this) -= a;
    }
    Gauss operator*(const Gauss &a) const {
        return Gauss(*this) *= a;
    }
    Gauss operator/(const Gauss &a) const {
        return Gauss(*this) /= a;
    }
    Gauss operator%(const Gauss &a) const {
        return Gauss(*this) %= a;
    }
    bool operator==(const Gauss &a) {
        return (x == a.x and y == a.y);
    }
    bool operator!=(const Gauss &a) {
        return (x != a.x or y != a.y);
    }
};

template <typename T> Gauss<T> gcd(Gauss<T> a, Gauss<T> b) {
    while (b != Gauss<T>(0, 0)) {
        a %= b;
        swap(a, b);
    }
    return a;
}

/**
 * @brief Gaussaussian Integer
 */
#line 5 "Math/twosquare.hpp"

vector<pair<ll, ll>> RepresentTwoSquare(ll n) {
    auto find = [&](ll p) -> Gauss<ll> {
        assert(p % 4 == 1);
        ll g = 1, x = -1;
        for (;;) {
            g++;
            x = mpow(g, (p - 1) / 4, p);
            if ((__int128_t(x) * x) % p == p - 1)
                break;
        }
        Gauss<ll> a(p, 0), b(x, 1);
        a = gcd(a, b);
        assert(a.norm() == p);
        return a;
    };
    auto subtask = [&](ll p, int e) -> vector<Gauss<ll>> {
        if (p == 2) {
            Gauss<ll> ret(1, 0), b(1, 1);
            rep(_, 0, e) ret *= b;
            return {ret};
        } else if (p % 4 == 1) {
            auto base = find(p);
            vector<Gauss<ll>> pws(e + 1), ret(e + 1);
            pws[0] = Gauss<ll>(1, 0);
            rep(i, 0, e) pws[i + 1] = pws[i] * base;
            rep(i, 0, e + 1) ret[i] = pws[i] * pws[e - i].conj();
            return ret;
        } else {
            if (e & 1)
                return {};
            ll q = 1;
            rep(_, 0, e / 2) q *= p;
            return {Gauss<ll>(q, 0)};
        }
    };

    if (n == 0) {
        return {{0, 0}};
    }
    auto ps = Pollard(n);
    map<ll, int> pe;
    for (auto &p : ps)
        pe[p]++;
    vector<Gauss<ll>> ret;
    ret.push_back(Gauss<ll>(1, 0));
    for (auto &[p, e] : pe) {
        auto add = subtask(p, e);
        vector<Gauss<ll>> nxt;
        for (auto &x : ret) {
            for (auto &y : add) {
                nxt.push_back(x * y);
            }
        }
        swap(ret, nxt);
    }
    vector<pair<ll, ll>> out;
    for (auto x : ret) {
        rep(_, 0, 4) {
            swap(x.x, x.y);
            x.x *= -1;
            if (x.x >= 0 and x.y >= 0) {
                out.push_back({x.x, x.y});
            }
        }
    }
    return out;
}

/**
 * @brief Represent A Number As Two Square Sum
 */
Back to top page