結果
問題 | No.1287 えぬけー |
ユーザー | NyaanNyaan |
提出日時 | 2020-11-13 21:22:30 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 146 ms / 2,000 ms |
コード長 | 20,093 bytes |
コンパイル時間 | 4,838 ms |
コンパイル使用メモリ | 350,272 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-22 20:24:50 |
合計ジャッジ時間 | 5,922 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,816 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | AC | 2 ms
6,944 KB |
testcase_04 | AC | 2 ms
6,944 KB |
testcase_05 | AC | 142 ms
6,940 KB |
testcase_06 | AC | 141 ms
6,944 KB |
testcase_07 | AC | 146 ms
6,940 KB |
testcase_08 | AC | 134 ms
6,940 KB |
ソースコード
/*** date : 2020-11-13 21:22:26*/#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";elsecerr << c;}void _cout(const unsigned int &c) {if (c == 1001001001)cerr << "inf";elsecerr << 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";elsecerr << c;}void _cout(const unsigned long long &c) {if (c == 1001001001 || c == (1LL << 61) - 1)cerr << "inf";elsecerr << 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(...)#endifinline 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 endregionusing 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 innerusing 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;namespace my_rand {uint64_t rng() {#ifdef NyaanDebugstatic uint64_t x_ =chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count();#elsestatic uint64_t x_ = 88172645463325252ULL;#endifx_ = x_ ^ (x_ << 7);return x_ = x_ ^ (x_ >> 9);}// [l, r)int64_t randint(int64_t l, int64_t r) {assert(l < r);return l + rng() % (r - l);}//vector<int64_t> randset(int64_t l, int64_t r, int64_t n) {assert(l <= r && n <= r - l);unordered_set<int64_t> s;for (int64_t i = n; i; --i) {int64_t m = randint(l, r + 1 - i);if (s.find(m) != s.end()) m = r - i;s.insert(m);}vector<int64_t> ret;for (auto& x : s) ret.push_back(x);return ret;}} // namespace my_randusing my_rand::randint;using my_rand::randset;using my_rand::rng;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});elsereturn 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) dog = 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);elsep = 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;}using i64 = int64_t;map<u64, i64> factor_count(u64 n) {map<u64, i64> mp;for (auto &x : factorize(n)) mp[x]++;return mp;}vector<u64> divisors(u64 n) {if (n == 0) return {};vector<pair<u64, i64>> v;for (auto &p : factor_count(n)) v.push_back(p);vector<u64> ret;auto f = [&](auto rec, int i, u64 x) -> void {if (i == (int)v.size()) {ret.push_back(x);return;}for (int j = v[i].second;; --j) {rec(rec, i + 1, x);if (j == 0) break;x *= v[i].first;}};f(f, 0, 1);sort(begin(ret), end(ret));return ret;}} // namespace fast_factorizeusing fast_factorize::divisors;using fast_factorize::factor_count;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-GStemplate <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) ) = 1mint 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);elsereturn inner_kth_root<int64_t, __int128_t, montgomery64>(a, k, p);}} // namespace kth_root_modusing kth_root_mod::kth_root;/*** @brief kth root(Tonelli-Shanks algorithm)* @docs docs/modulo/mod-kth-root.md*/void solve(){ini(T);rep(_,T){ini(x,k);out(kth_root(x,k,1000000007));}}