#579734 (C++14) No.1287 えぬけー

• 問題: No.1287 えぬけー
• ユーザー: Rubikun
• 提出日時: 2020-11-13 22:49:18
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 148 ms / 2,000 ms
• コード長: 21,051 bytes
• コンパイル時間: 3,727 ms
• コンパイル使用メモリ: 301,500 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-07-22 21:49:13
• 合計ジャッジ時間: 5,176 ms
• ジャッジサーバーID （参考情報）: judge1 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	2 ms; 5,376 KB
testcase_05	AC	141 ms; 5,376 KB
testcase_06	AC	143 ms; 5,376 KB
testcase_07	AC	148 ms; 5,376 KB
testcase_08	AC	136 ms; 5,376 KB

ソースコード

// from https://judge.yosupo.jp/submission/23481

#pragma region kyopro_template
#define Nyaan_template
#include <immintrin.h>
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define each(x, v) for (auto &x : v)
#define all(v) (v).begin(), (v).end()
#define sz(v) ((int)(v).size())
#define mem(a, val) memset(a, val, sizeof(a))
#define ini(...)   \
int __VA_ARGS__; \
in(__VA_ARGS__)
#define inl(...)         \
long long __VA_ARGS__; \
in(__VA_ARGS__)
#define ins(...)      \
string __VA_ARGS__; \
in(__VA_ARGS__)
#define inc(...)    \
char __VA_ARGS__; \
in(__VA_ARGS__)
#define in2(s, t)                           \
for (int i = 0; i < (int)s.size(); i++) { \
in(s[i], t[i]);                         \
}
#define in3(s, t, u)                        \
for (int i = 0; i < (int)s.size(); i++) { \
in(s[i], t[i], u[i]);                   \
}
#define in4(s, t, u, v)                     \
for (int i = 0; i < (int)s.size(); i++) { \
in(s[i], t[i], u[i], v[i]);             \
}
#define rep(i, N) for (long long i = 0; i < (long long)(N); i++)
#define repr(i, N) for (long long i = (long long)(N)-1; i >= 0; i--)
#define rep1(i, N) for (long long i = 1; i <= (long long)(N); i++)
#define repr1(i, N) for (long long i = (N); (long long)(i) > 0; i--)
#define reg(i, a, b) for (long long i = (a); i < (b); i++)
#define die(...)      \
do {                \
out(__VA_ARGS__); \
return;           \
} while (0)
using namespace std;
using ll = long long;
template <class T>
using V = vector<T>;
using vi = vector<int>;
using vl = vector<long long>;
using vvi = vector<vector<int>>;
using vd = V<double>;
using vs = V<string>;
using vvl = vector<vector<long long>>;
using P = pair<long long, long long>;
using vp = vector<P>;
using pii = pair<int, int>;
using vpi = vector<pair<int, int>>;
constexpr int inf = 1001001001;
constexpr long long infLL = (1LL << 61) - 1;
template <typename T, typename U>
inline bool amin(T &x, U y) {
    return (y < x) ? (x = y, true) : false;
}
template <typename T, typename U>
inline bool amax(T &x, U y) {
    return (x < y) ? (x = y, true) : false;
}
template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
    os << p.first << " " << p.second;
    return os;
}
template <typename T, typename U>
istream &operator>>(istream &is, pair<T, U> &p) {
    is >> p.first >> p.second;
    return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    int s = (int)v.size();
    for (int i = 0; i < s; i++) os << (i ? " " : "") << v[i];
    return os;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
    for (auto &x : v) is >> x;
    return is;
}
void in() {}
template <typename T, class... U>
void in(T &t, U &... u) {
    cin >> t;
    in(u...);
}
void out() { cout << "\n"; }
template <typename T, class... U>
void out(const T &t, const U &... u) {
    cout << t;
    if (sizeof...(u)) cout << " ";
    out(u...);
}

#ifdef NyaanDebug
#define trc(...)                   \
do {                             \
cerr << #__VA_ARGS__ << " = "; \
dbg_out(__VA_ARGS__);          \
} while (0)
#define trca(v, N)       \
do {                   \
cerr << #v << " = "; \
array_out(v, N);     \
} while (0)
#define trcc(v)                             \
do {                                      \
cerr << #v << " = {";                   \
each(x, v) { cerr << " " << x << ","; } \
cerr << "}" << endl;                    \
} while (0)
template <typename T>
void _cout(const T &c) {
    cerr << c;
}
void _cout(const int &c) {
    if (c == 1001001001)
        cerr << "inf";
    else if (c == -1001001001)
        cerr << "-inf";
    else
        cerr << c;
}
void _cout(const unsigned int &c) {
    if (c == 1001001001)
        cerr << "inf";
    else
        cerr << c;
}
void _cout(const long long &c) {
    if (c == 1001001001 || c == (1LL << 61) - 1)
        cerr << "inf";
    else if (c == -1001001001 || c == -((1LL << 61) - 1))
        cerr << "-inf";
    else
        cerr << c;
}
void _cout(const unsigned long long &c) {
    if (c == 1001001001 || c == (1LL << 61) - 1)
        cerr << "inf";
    else
        cerr << c;
}
template <typename T, typename U>
void _cout(const pair<T, U> &p) {
    cerr << "{ ";
    _cout(p.fi);
    cerr << ", ";
    _cout(p.se);
    cerr << " } ";
}
template <typename T>
void _cout(const vector<T> &v) {
    int s = v.size();
    cerr << "{ ";
    for (int i = 0; i < s; i++) {
        cerr << (i ? ", " : "");
        _cout(v[i]);
    }
    cerr << " } ";
}
template <typename T>
void _cout(const vector<vector<T>> &v) {
    cerr << "[ ";
    for (const auto &x : v) {
        cerr << endl;
        _cout(x);
        cerr << ", ";
    }
    cerr << endl << " ] ";
}
void dbg_out() { cerr << endl; }
template <typename T, class... U>
void dbg_out(const T &t, const U &... u) {
    _cout(t);
    if (sizeof...(u)) cerr << ", ";
    dbg_out(u...);
}
template <typename T>
void array_out(const T &v, int s) {
    cerr << "{ ";
    for (int i = 0; i < s; i++) {
        cerr << (i ? ", " : "");
        _cout(v[i]);
    }
    cerr << " } " << endl;
}
template <typename T>
void array_out(const T &v, int H, int W) {
    cerr << "[ ";
    for (int i = 0; i < H; i++) {
        cerr << (i ? ", " : "");
        array_out(v[i], W);
    }
    cerr << " ] " << endl;
}
#else
#define trc(...)
#define trca(...)
#define trcc(...)
#endif

inline int popcnt(unsigned long long a) { return __builtin_popcountll(a); }
inline int lsb(unsigned long long a) { return __builtin_ctzll(a); }
inline int msb(unsigned long long a) { return 63 - __builtin_clzll(a); }
template <typename T>
inline int getbit(T a, int i) {
    return (a >> i) & 1;
}
template <typename T>
inline void setbit(T &a, int i) {
    a |= (1LL << i);
}
template <typename T>
inline void delbit(T &a, int i) {
    a &= ~(1LL << i);
}
template <typename T>
int lb(const vector<T> &v, const T &a) {
    return lower_bound(begin(v), end(v), a) - begin(v);
}
template <typename T>
int ub(const vector<T> &v, const T &a) {
    return upper_bound(begin(v), end(v), a) - begin(v);
}
template <typename T>
int btw(T a, T x, T b) {
    return a <= x && x < b;
}
template <typename T, typename U>
T ceil(T a, U b) {
    return (a + b - 1) / b;
}
constexpr long long TEN(int n) {
    long long ret = 1, x = 10;
    while (n) {
        if (n & 1) ret *= x;
        x *= x;
        n >>= 1;
    }
    return ret;
}
template <typename T>
vector<T> mkrui(const vector<T> &v) {
    vector<T> ret(v.size() + 1);
    for (int i = 0; i < int(v.size()); i++) ret[i + 1] = ret[i] + v[i];
    return ret;
};
template <typename T>
vector<T> mkuni(const vector<T> &v) {
    vector<T> ret(v);
    sort(ret.begin(), ret.end());
    ret.erase(unique(ret.begin(), ret.end()), ret.end());
    return ret;
}
template <typename F>
vector<int> mkord(int N, F f) {
    vector<int> ord(N);
    iota(begin(ord), end(ord), 0);
    sort(begin(ord), end(ord), f);
    return ord;
}
template <typename T = int>
vector<T> mkiota(int N) {
    vector<T> ret(N);
    iota(begin(ret), end(ret), 0);
    return ret;
}
template <typename T>
vector<int> mkinv(vector<T> &v) {
    vector<int> inv(v.size());
    for (int i = 0; i < (int)v.size(); i++) inv[v[i]] = i;
    return inv;
}

struct IoSetupNya {
    IoSetupNya() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(15);
        cerr << fixed << setprecision(7);
    }
} iosetupnya;

void solve();
int main() { solve(); }

#pragma endregion
using namespace std;

using namespace std;

namespace inner {
    
    using i32 = int32_t;
    using u32 = uint32_t;
    using i64 = int64_t;
    using u64 = uint64_t;
    
    template <typename T>
    T gcd(T a, T b) {
        while (b) swap(a %= b, b);
        return a;
    }
    
    template <typename T>
    T inv(T a, T p) {
        T b = p, x = 1, y = 0;
        while (a) {
            T q = b / a;
            swap(a, b %= a);
            swap(x, y -= q * x);
        }
        assert(b == 1);
        return y < 0 ? y + p : y;
    }
    
    template <typename T, typename U>
    T modpow(T a, U n, T p) {
        T ret = 1 % p;
        for (; n; n >>= 1, a = U(a) * a % p)
            if (n & 1) ret = U(ret) * a % p;
        return ret;
    }
    
}  // namespace inner
using namespace std;

struct ArbitraryLazyMontgomeryModInt {
    using mint = ArbitraryLazyMontgomeryModInt;
    using i32 = int32_t;
    using u32 = uint32_t;
    using u64 = uint64_t;
    
    static u32 mod;
    static u32 r;
    static u32 n2;
    
    static u32 get_r() {
        u32 ret = mod;
        for (i32 i = 0; i < 4; ++i) ret *= 2 - mod * ret;
        return ret;
    }
    
    static void set_mod(u32 m) {
        assert(m < (1 << 30));
        assert((m & 1) == 1);
        mod = m;
        n2 = -u64(m) % m;
        r = get_r();
        assert(r * mod == 1);
    }
    
    u32 a;
    
    ArbitraryLazyMontgomeryModInt() : a(0) {}
    ArbitraryLazyMontgomeryModInt(const int64_t &b)
    : a(reduce(u64(b % mod + mod) * n2)){};
    
    static u32 reduce(const u64 &b) {
        return (b + u64(u32(b) * u32(-r)) * mod) >> 32;
    }
    
    mint &operator+=(const mint &b) {
        if (i32(a += b.a - 2 * mod) < 0) a += 2 * mod;
        return *this;
    }
    
    mint &operator-=(const mint &b) {
        if (i32(a -= b.a) < 0) a += 2 * mod;
        return *this;
    }
    
    mint &operator*=(const mint &b) {
        a = reduce(u64(a) * b.a);
        return *this;
    }
    
    mint &operator/=(const mint &b) {
        *this *= b.inverse();
        return *this;
    }
    
    mint operator+(const mint &b) const { return mint(*this) += b; }
    mint operator-(const mint &b) const { return mint(*this) -= b; }
    mint operator*(const mint &b) const { return mint(*this) *= b; }
    mint operator/(const mint &b) const { return mint(*this) /= b; }
    bool operator==(const mint &b) const {
        return (a >= mod ? a - mod : a) == (b.a >= mod ? b.a - mod : b.a);
    }
    bool operator!=(const mint &b) const {
        return (a >= mod ? a - mod : a) != (b.a >= mod ? b.a - mod : b.a);
    }
    mint operator-() const { return mint() - mint(*this); }
    
    mint pow(u64 n) const {
        mint ret(1), mul(*this);
        while (n > 0) {
            if (n & 1) ret *= mul;
            mul *= mul;
            n >>= 1;
        }
        return ret;
    }
    
    friend ostream &operator<<(ostream &os, const mint &b) {
        return os << b.get();
    }
    
    friend istream &operator>>(istream &is, mint &b) {
        int64_t t;
        is >> t;
        b = ArbitraryLazyMontgomeryModInt(t);
        return (is);
    }
    
    mint inverse() const { return pow(mod - 2); }
    
    u32 get() const {
        u32 ret = reduce(a);
        return ret >= mod ? ret - mod : ret;
    }
    
    static u32 get_mod() { return mod; }
};
typename ArbitraryLazyMontgomeryModInt::u32 ArbitraryLazyMontgomeryModInt::mod;
typename ArbitraryLazyMontgomeryModInt::u32 ArbitraryLazyMontgomeryModInt::r;
typename ArbitraryLazyMontgomeryModInt::u32 ArbitraryLazyMontgomeryModInt::n2;
using namespace std;

struct montgomery64 {
    using mint = montgomery64;
    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;
        for (i64 i = 0; i < 5; ++i) 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);
    }
    
    u64 a;
    
    montgomery64() : a(0) {}
    montgomery64(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;
    }
    
    mint &operator+=(const mint &b) {
        if (i64(a += b.a - 2 * mod) < 0) a += 2 * mod;
        return *this;
    }
    
    mint &operator-=(const mint &b) {
        if (i64(a -= b.a) < 0) a += 2 * mod;
        return *this;
    }
    
    mint &operator*=(const mint &b) {
        a = reduce(u128(a) * b.a);
        return *this;
    }
    
    mint &operator/=(const mint &b) {
        *this *= b.inverse();
        return *this;
    }
    
    mint operator+(const mint &b) const { return mint(*this) += b; }
    mint operator-(const mint &b) const { return mint(*this) -= b; }
    mint operator*(const mint &b) const { return mint(*this) *= b; }
    mint operator/(const mint &b) const { return mint(*this) /= b; }
    bool operator==(const mint &b) const {
        return (a >= mod ? a - mod : a) == (b.a >= mod ? b.a - mod : b.a);
    }
    bool operator!=(const mint &b) const {
        return (a >= mod ? a - mod : a) != (b.a >= mod ? b.a - mod : b.a);
    }
    mint operator-() const { return mint() - mint(*this); }
    
    mint pow(u128 n) const {
        mint ret(1), mul(*this);
        while (n > 0) {
            if (n & 1) ret *= mul;
            mul *= mul;
            n >>= 1;
        }
        return ret;
    }
    
    friend ostream &operator<<(ostream &os, const mint &b) {
        return os << b.get();
    }
    
    friend istream &operator>>(istream &is, mint &b) {
        int64_t t;
        is >> t;
        b = montgomery64(t);
        return (is);
    }
    
    mint inverse() const { return pow(mod - 2); }
    
    u64 get() const {
        u64 ret = reduce(a);
        return ret >= mod ? ret - mod : ret;
    }
    
    static u64 get_mod() { return mod; }
};
typename montgomery64::u64 montgomery64::mod, montgomery64::r, montgomery64::n2;
using namespace std;

using namespace std;

unsigned long long rng() {
    static unsigned long long x_ = 88172645463325252ULL;
    x_ = x_ ^ (x_ << 7);
    return x_ = x_ ^ (x_ >> 9);
}
namespace fast_factorize {
    using u64 = uint64_t;
    
    template <typename mint>
    bool miller_rabin(u64 n, vector<u64> as) {
        if (mint::get_mod() != n) mint::set_mod(n);
        u64 d = n - 1;
        while (~d & 1) d >>= 1;
        mint e{1}, rev{int64_t(n - 1)};
        for (u64 a : as) {
            if (n <= a) break;
            u64 t = d;
            mint y = mint(a).pow(t);
            while (t != n - 1 && y != e && y != rev) {
                y *= y;
                t *= 2;
            }
            if (y != rev && t % 2 == 0) return false;
        }
        return true;
    }
    
    bool is_prime(u64 n) {
        if (~n & 1) return n == 2;
        if (n <= 1) return false;
        if (n < (1LL << 30))
            return miller_rabin<ArbitraryLazyMontgomeryModInt>(n, {2, 7, 61});
        else
            return miller_rabin<montgomery64>(
                                              n, {2, 325, 9375, 28178, 450775, 9780504, 1795265022});
    }
    
    template <typename mint, typename T>
    T pollard_rho(T n) {
        if (~n & 1) return 2;
        if (is_prime(n)) return n;
        if (mint::get_mod() != n) mint::set_mod(n);
        mint R, one = 1;
        auto f = [&](mint x) { return x * x + R; };
        auto rnd = [&]() { return rng() % (n - 2) + 2; };
        while (1) {
            mint x, y, ys, q = one;
            R = rnd(), y = rnd();
            T g = 1;
            constexpr int m = 128;
            for (int r = 1; g == 1; r <<= 1) {
                x = y;
                for (int i = 0; i < r; ++i) y = f(y);
                for (int k = 0; g == 1 && k < r; k += m) {
                    ys = y;
                    for (int i = 0; i < m && i < r - k; ++i) q *= x - (y = f(y));
                    g = inner::gcd<T>(q.get(), n);
                }
            }
            if (g == n) do
                g = inner::gcd<T>((x - (ys = f(ys))).get(), n);
            while (g == 1);
            if (g != n) return g;
        }
        exit(1);
    }
    
    vector<u64> inner_factorize(u64 n) {
        if (n <= 1) return {};
        u64 p;
        if (n <= (1LL << 30))
            p = pollard_rho<ArbitraryLazyMontgomeryModInt, uint32_t>(n);
        else
            p = pollard_rho<montgomery64, uint64_t>(n);
        if (p == n) return {p};
        auto l = inner_factorize(p);
        auto r = inner_factorize(n / p);
        copy(begin(r), end(r), back_inserter(l));
        return l;
    }
    
    vector<u64> factorize(u64 n) {
        auto ret = inner_factorize(n);
        sort(begin(ret), end(ret));
        return ret;
    }
    
}  // namespace fast_factorize
using fast_factorize::factorize;
using fast_factorize::is_prime;

/**
 * @brief 高速素因数分解(Miller Rabin/Pollard's Rho)
 * @docs docs/prime/fast-factorize.md
 */

namespace kth_root_mod {
    
    // fast BS-GS
    template <typename T>
    struct Memo {
        Memo(const T &g, int s, int period)
        : size(1 << __lg(min(s, period))),
        mask(size - 1),
        period(period),
        vs(size),
        os(size + 1) {
            T x(1);
            for (int i = 0; i < size; ++i, x *= g) os[x.get() & mask]++;
            for (int i = 1; i < size; ++i) os[i] += os[i - 1];
            x = 1;
            for (int i = 0; i < size; ++i, x *= g) vs[--os[x.get() & mask]] = {x, i};
            gpow = x;
            os[size] = size;
        }
        int find(T x) const {
            for (int t = 0; t < period; t += size, x *= gpow) {
                for (int m = (x.get() & mask), i = os[m]; i < os[m + 1]; ++i) {
                    if (x == vs[i].first) {
                        int ret = vs[i].second - t;
                        return ret < 0 ? ret + period : ret;
                    }
                }
            }
            assert(0);
        }
        T gpow;
        int size, mask, period;
        vector<pair<T, int> > vs;
        vector<int> os;
    };
    
    using inner::gcd;
    using inner::inv;
    using inner::modpow;
    template <typename INT, typename LINT, typename mint>
    mint pe_root(INT c, INT pi, INT ei, INT p) {
        if (mint::get_mod() != decltype(mint::a)(p)) mint::set_mod(p);
        INT s = p - 1, t = 0;
        while (s % pi == 0) s /= pi, ++t;
        INT pe = 1;
        for (INT _ = 0; _ < ei; ++_) pe *= pi;
        
        INT u = inv(pe - s % pe, pe);
        mint mc = c, one = 1;
        mint z = mc.pow((s * u + 1) / pe);
        mint zpe = mc.pow(s * u);
        if (zpe == one) return z;
        
        assert(t > ei);
        mint vs;
        {
            INT ptm1 = 1;
            for (INT _ = 0; _ < t - 1; ++_) ptm1 *= pi;
            for (mint v = 2;; v += one) {
                vs = v.pow(s);
                if (vs.pow(ptm1) != one) break;
            }
        }
        
        mint vspe = vs.pow(pe);
        INT vs_e = ei;
        mint base = vspe;
        for (INT _ = 0; _ < t - ei - 1; _++) base = base.pow(pi);
        Memo<mint> memo(base, (INT)(sqrt(t - ei) * sqrt(pi)) + 1, pi);
        
        while (zpe != one) {
            mint tmp = zpe;
            INT td = 0;
            while (tmp != 1) ++td, tmp = tmp.pow(pi);
            INT e = t - td;
            while (vs_e != e) {
                vs = vs.pow(pi);
                vspe = vspe.pow(pi);
                ++vs_e;
            }
            
            // BS-GS ... find (zpe * ( vspe ^ n ) ) ^( p_i ^ (td - 1) ) = 1
            mint base_zpe = zpe.inverse();
            for (INT _ = 0; _ < td - 1; _++) base_zpe = base_zpe.pow(pi);
            INT bsgs = memo.find(base_zpe);
            
            z *= vs.pow(bsgs);
            zpe *= vspe.pow(bsgs);
        }
        return z;
    }
    
    template <typename INT, typename LINT, typename mint>
    INT inner_kth_root(INT a, INT k, INT p) {
        a %= p;
        if (k == 0) return a == 1 ? a : -1;
        if (a <= 1 || k <= 1) return a;
        
        assert(p > 2);
        if (mint::get_mod() != decltype(mint::a)(p)) mint::set_mod(p);
        INT g = gcd(p - 1, k);
        if (modpow<INT, LINT>(a, (p - 1) / g, p) != 1) return -1;
        a = mint(a).pow(inv(k / g, (p - 1) / g)).get();
        unordered_map<INT, int> fac;
        for (auto &f : factorize(g)) fac[f]++;
        if (mint::get_mod() != decltype(mint::a)(p)) mint::set_mod(p);
        for (auto pp : fac)
            a = pe_root<INT, LINT, mint>(a, pp.first, pp.second, p).get();
        return a;
    }
    
    int64_t kth_root(int64_t a, int64_t k, int64_t p) {
        if (max({a, k, p}) < (1LL << 30))
            return inner_kth_root<int32_t, int64_t, ArbitraryLazyMontgomeryModInt>(a, k,
                                                                                   p);
        else
            return inner_kth_root<int64_t, __int128_t, montgomery64>(a, k, p);
    }
    
}  // namespace kth_root_mod
using kth_root_mod::kth_root;

/**
 * @brief kth root(Tonelli-Shanks algorithm)
 * @docs docs/modulo/mod-kth-root.md
 */

const int PP=1000000007;

void solve() {
    ini(T);
    rep(_, T) {
        inl(X, K);
        int ans = kth_root(X, K, PP);
        out(ans);
    }
}