結果
問題 |
No.3236 累乗数大好きbot
|
ユーザー |
|
提出日時 | 2025-08-15 22:59:57 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 25,172 bytes |
コンパイル時間 | 3,281 ms |
コンパイル使用メモリ | 301,328 KB |
実行使用メモリ | 12,120 KB |
最終ジャッジ日時 | 2025-08-15 23:00:27 |
合計ジャッジ時間 | 11,157 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 4 TLE * 1 -- * 26 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using vl = vector<ll>; using vvl = vector<vl>; using vvvl = vector<vvl>; using xy = pair<ll, ll>; using vxy = vector<xy>; using vvxy = vector<vxy>; using bs8 = bitset<8>; using bs16 = bitset<16>; using bs32 = bitset<32>; using bs64 = bitset<64>; using vbs8 = vector<bs8>; using vbs16 = vector<bs16>; using vbs32 = vector<bs32>; using vbs64 = vector<bs64>; using vs = vector<string>; using vvs = vector<vs>; using ull = unsigned long long; using vul = vector<ull>; using vd = vector<double>; using vvd = vector<vd>; using coord = pair<double, double>; using vcoord = vector<coord>; #define rep(var, n) for (ll var = 0; var < (ll)(n); var++) #define cnt(var, n, m) for (ll var = (n); var <= (ll)(m); var++) #define rcnt(var, n, m) for (ll var = (n); var >= (ll)(m); var--) #define each(ite, C) for (auto ite = (C).begin(); ite != (C).end(); ite++) #define reach(ite, C) for (auto ite = (C).rbegin(); ite != (C).rend(); ite++) #define yn(b) cout << (((b) > 0) ? "Yes" : "No") << endl; ///////////////////////////////////////////////// namespace zz_print { class dbg { public: static bool unprint; static string margin; static string separated; static string indentS; static int hierarchical; static int topHier; static int precision; static bool exponential; static void setFloat(const int& prec, const bool& expo) { precision = prec; exponential = expo; }; private: static void ZOUT(const ll& x, const bool& tail = false) { cout << x; if (tail) { cout << margin << flush; } else { cout << separated << flush; } }; static void ZOUT(const ull& x, const bool& tail = false) { cout << x; if (tail) { cout << margin << flush; } else { cout << separated << flush; } }; static void ZOUT(const int& x, const bool& tail = false) { cout << x; if (tail) { cout << margin << flush; } else { cout << separated << flush; } }; static void ZOUT(const unsigned int& x, const bool& tail = false) { cout << x; if (tail) { cout << margin << flush; } else { cout << separated << flush; } }; static void ZOUT(const double& x, const bool& tail = false) { cout << x; if (tail) { cout << margin << flush; } else { cout << separated << flush; } }; static void ZOUT(const float& x, const bool& tail = false) { cout << x; if (tail) { cout << margin << flush; } else { cout << separated << flush; } }; static void ZOUT(const char& x, const bool& tail = false) { cout << x; if (tail) { cout << margin << flush; } else { cout << separated << flush; } }; static void ZOUT(const string& x, const bool& tail = false) { cout << x; if (tail) { cout << margin << flush; } else { cout << separated << flush; } }; static void ZOUT(const bs8& x, const bool& tail = false) { cout << x; if (tail) { cout << margin << flush; } else { cout << separated << flush; } }; static void ZOUT(const bs16& x, const bool& tail = false) { cout << x; if (tail) { cout << margin << flush; } else { cout << separated << flush; } }; static void ZOUT(const bs32& x, const bool& tail = false) { cout << x; if (tail) { cout << margin << flush; } else { cout << separated << flush; } }; static void ZOUT(const bs64& x, const bool& tail = false) { cout << x; if (tail) { cout << margin << flush; } else { cout << separated << flush; } }; template <typename T> static void ZOUT(const T& x, const bool& tail = false) { cout << x; if (tail) { cout << margin << flush; } else { cout << separated << flush; } }; static bool BRANKET_BEGIN(const char& c_L) { cout << c_L << margin; if (hierarchical > 0) { hierarchical--; indentS.push_back(' '); indentS += margin; cout << endl << indentS; return false; } return true; }; static void BRANKET_END(const char& c_R, const bool& flat, const bool& tail = false) { if (!flat) { rep(i, 1 + margin.size()) indentS.pop_back(); cout << endl << indentS; } cout << c_R; if (tail) { cout << margin << flush; } else { cout << separated << flush; } if (!flat) { hierarchical++; if (hierarchical == topHier) cout << endl << indentS; } }; template <typename Elm> static void ZOUT(const vector<Elm>& x, const bool& tail = false) { bool flat = BRANKET_BEGIN('['); ll I = 0; ll N = x.size() - 1; each(ite, x) { ZOUT(*ite, (I == N)); if (!flat && I != N) cout << endl << indentS; I++; } BRANKET_END(']', flat, tail); }; template <typename Elm> static void ZOUT(const list<Elm>& x, const bool& tail = false) { bool flat = BRANKET_BEGIN('('); ll I = 0; ll N = x.size() - 1; each(ite, x) { ZOUT(*ite, (I == N)); if (!flat && I != N) cout << endl << indentS; I++; } BRANKET_END(')', flat, tail); }; template <typename LftElm, typename RgtElm> static void ZOUT(const pair<LftElm, RgtElm>& x, const bool& tail = false) { bool flat = BRANKET_BEGIN('<'); ZOUT(x.first); if (!flat) cout << endl << indentS; ZOUT(x.second, true); BRANKET_END('>', flat, tail); }; template <typename LftElm, typename RgtElm> static void ZOUT(const map<LftElm, RgtElm>& x, const bool& tail = false) { bool flat = BRANKET_BEGIN('{'); ll I = 0; ll N = x.size() - 1; each(ite, x) { ZOUT(*ite, (I == N)); if (!flat && I != N) cout << endl << indentS; I++; } BRANKET_END('}', flat, tail); }; template <typename LftElm, typename RgtElm> static void ZOUT(const multimap<LftElm, RgtElm>& x, const bool& tail = false) { bool flat = BRANKET_BEGIN('{'); ll I = 0; ll N = x.size() - 1; each(ite, x) { ZOUT(*ite, (I == N)); if (!flat && I != N) cout << endl << indentS; I++; } BRANKET_END('}', flat, tail); }; template <typename LftElm, typename RgtElm> static void ZOUT(const unordered_map<LftElm, RgtElm>& x, const bool& tail = false) { bool flat = BRANKET_BEGIN('{'); ll I = 0; ll N = x.size() - 1; each(ite, x) { ZOUT(*ite, (I == N)); if (!flat && I != N) cout << endl << indentS; I++; } BRANKET_END('}', flat, tail); }; template <typename LftElm, typename RgtElm> static void ZOUT(const unordered_multimap<LftElm, RgtElm>& x, const bool& tail = false) { bool flat = BRANKET_BEGIN('{'); ll I = 0; ll N = x.size() - 1; each(ite, x) { ZOUT(*ite, (I == N)); if (!flat && I != N) cout << endl << indentS; I++; } BRANKET_END('}', flat, tail); }; template <typename Elm> static void ZOUT(const set<Elm>& x, const bool& tail = false) { bool flat = BRANKET_BEGIN('{'); ll I = 0; ll N = x.size() - 1; each(ite, x) { ZOUT(*ite, (I == N)); if (!flat && I != N) cout << endl << indentS; I++; } BRANKET_END('}', flat, tail); }; template <typename Elm> static void ZOUT(const multiset<Elm>& x, const bool& tail = false) { bool flat = BRANKET_BEGIN('{'); ll I = 0; ll N = x.size() - 1; each(ite, x) { ZOUT(*ite, (I == N)); if (!flat && I != N) cout << endl << indentS; I++; } BRANKET_END('}', flat, tail); }; template <typename Elm> static void ZOUT(const unordered_set<Elm>& x, const bool& tail = false) { bool flat = BRANKET_BEGIN('{'); ll I = 0; ll N = x.size() - 1; each(ite, x) { ZOUT(*ite, (I == N)); if (!flat && I != N) cout << endl << indentS; I++; } BRANKET_END('}', flat, tail); }; template <typename Elm> static void ZOUT(const unordered_multiset<Elm>& x, const bool& tail = false) { bool flat = BRANKET_BEGIN('{'); ll I = 0; ll N = x.size() - 1; each(ite, x) { ZOUT(*ite, (I == N)); if (!flat && I != N) cout << endl << indentS; I++; } BRANKET_END('}', flat, tail); }; template <typename Elm> static void ZOUT(const stack<Elm>& x, const bool& tail = false) { bool flat = BRANKET_BEGIN('['); stack<Elm> y = x; while (!y.empty()) { ZOUT(y.top(), y.size() == 1); y.pop(); if (!flat && !y.empty()) cout << endl << indentS; } BRANKET_END(')', flat, tail); }; template <typename Elm> static void ZOUT(const queue<Elm>& x, const bool& tail = false) { bool flat = BRANKET_BEGIN('['); queue<Elm> y = x; while (!y.empty()) { ZOUT(y.front(), y.size() == 1); y.pop(); if (!flat && !y.empty()) cout << endl << indentS; } BRANKET_END(')', flat, tail); }; template <typename Elm> static void ZOUT(const priority_queue<Elm>& x, const bool& tail = false) { bool flat = BRANKET_BEGIN('['); priority_queue<Elm> y = x; while (!y.empty()) { ZOUT(y.top(), y.size() == 1); y.pop(); if (!flat && !y.empty()) cout << endl << indentS; } BRANKET_END(')', flat, tail); }; template <typename Elm> static void ZOUT(const deque<Elm>& x, const bool& tail = false) { bool flat = BRANKET_BEGIN('['); deque<Elm> y = x; while (!y.empty()) { ZOUT(y.front(), y.size() == 1); y.pop_front(); if (!flat && !y.empty()) cout << endl << indentS; } BRANKET_END(']', flat, tail); }; static void ZOUT_BRANCH() {} template <typename HeadArg, typename... Args> static void ZOUT_BRANCH(HeadArg&& head, Args&&... args) { ZOUT(head); ZOUT_BRANCH(forward<Args>(args)...); }; public: template <int hier = 0, int sep = 2, int mgn = 1, typename... Args> static void zout(Args&&... args) { if (unprint) return; margin = string(mgn, ' '); separated = string(sep, ' '); hierarchical = hier; topHier = hier; indentS = ""; cout << setprecision(precision); if (exponential) { cout << scientific; } else { cout << fixed; } ZOUT_BRANCH(forward<Args>(args)...); cout << endl << defaultfloat; }; }; bool dbg::unprint = false; string dbg::margin = ""; string dbg::separated = ""; string dbg::indentS = ""; int dbg::hierarchical = 0; int dbg::topHier = 0; int dbg::precision = 6; bool dbg::exponential = false; }; // namespace zz_print using namespace zz_print; namespace zz_time { /// @brief プログラム実行時のタイムポイント std::chrono::_V2::system_clock::time_point START_TIME = std::chrono::system_clock::now(); /// @brief プログラム実行から経過時間をミリ秒で取得 /// @param st 経過開始時刻(基本引数指定する必要なし) /// @return 経過時間ミリ秒 ll currentTime(std::chrono::_V2::system_clock::time_point st = START_TIME) { std::chrono::_V2::system_clock::time_point now = std::chrono::system_clock::now(); return (ll)(std::chrono::duration_cast<std::chrono::milliseconds>(now - st) .count()); }; /// @brief 実行時間が超過していないかの判定 /// @param mSec 実行時間制約ミリ秒 /// @return 実行時間制約以下であればtrue,その他はfalse bool punctualityTime(const ll& mSec) { return (currentTime() < mSec); } /// @brief 実行時間が超過しているかの判定 /// @param mSec 実行時間制約ミリ秒 /// @return 実行時間制約超過していればtrue,その他はfalse bool spendTime(const ll& mSec) { return (currentTime() >= mSec); } }; // namespace zz_time using namespace zz_time; namespace zz_random { random_device seed_gen; default_random_engine RANDOM_ENGINE(seed_gen()); /// @brief 整数閉区間[L,R]一様ランダム器生成 /// @param L 下限値 (default 0) /// @param R 上限値 (default 1) /// @return ランダム生成器, RAMDOM_ENGINEを引数としてランダム生成 uniform_int_distribution<> createIntCloseSegRandom(const ll& L = 0, const ll& R = 1) { return uniform_int_distribution<>(L, R); }; /// @brief 実数閉区間[L,R]一様ランダム器生成 /// @param L 下限値 (default 0.0) /// @param R 上限値 (default 1.0) /// @return ランダム生成器, RAMDOM_ENGINEを引数としてランダム生成 uniform_real_distribution<> createRealCloseSegRandom(const double& L = 0.0, const double& R = 1.0) { return uniform_real_distribution<>(L, R); }; /// @brief 正規表現ランダム器生成 /// @param average 平均値 /// @param s 標準偏差 /// @return ランダム生成器, RAMDOM_ENGINEを引数としてランダム生成 normal_distribution<> createNormalRandom(const double& average = 0.0, const double& s = 1.0) { return normal_distribution<>(average, s); }; }; // namespace zz_random using namespace zz_random; namespace zz_mod { class pp { public: ll val; ll mod; static bool ignorePPModPrint; void recalc() { val %= mod; if (val < 0) val += mod; }; /// @brief modint (+-*/ != exp ~ inv recalc ) /// @param x value /// @param y mod (default= 998244353) pp(const ll& x = 0, const ll& y = 998244353) { val = x; mod = y; recalc(); }; friend pp operator+(const pp& x, const pp& y) { return pp(x.val + y.val, x.mod); }; friend pp operator+(const pp&& x, const pp& y) { return pp(x.val + y.val, x.mod); }; friend pp operator+(const pp& x, const pp&& y) { return pp(x.val + y.val, x.mod); }; friend pp operator+(const pp&& x, const pp&& y) { return pp(x.val + y.val, x.mod); }; template <typename T> friend pp operator+(const pp& x, const T& y) { return pp(x.val + y, x.mod); }; template <typename T> friend pp operator+(const pp&& x, const T& y) { return pp(x.val + y, x.mod); }; template <typename T> friend pp operator+(const pp& x, const T&& y) { return pp(x.val + y, x.mod); }; template <typename T> friend pp operator+(const pp&& x, const T&& y) { return pp(x.val + y, x.mod); }; friend pp operator-(const pp& x) { return pp(-x.val, x.mod); }; friend pp operator-(const pp&& x) { return pp(-x.val, x.mod); }; friend pp operator-(const pp& x, const pp& y) { return pp(x.val - y.val, x.mod); }; friend pp operator-(const pp&& x, const pp& y) { return pp(x.val - y.val, x.mod); }; friend pp operator-(const pp& x, const pp&& y) { return pp(x.val - y.val, x.mod); }; friend pp operator-(const pp&& x, const pp&& y) { return pp(x.val - y.val, x.mod); }; template <typename T> friend pp operator-(const pp& x, const T& y) { return pp(x.val - y, x.mod); }; template <typename T> friend pp operator-(const pp&& x, const T& y) { return pp(x.val - y, x.mod); }; template <typename T> friend pp operator-(const pp& x, const T&& y) { return pp(x.val - y, x.mod); }; template <typename T> friend pp operator-(const pp&& x, const T&& y) { return pp(x.val - y, x.mod); }; friend pp operator*(const pp& x, const pp& y) { return pp(x.val * y.val, x.mod); }; friend pp operator*(const pp&& x, const pp& y) { return pp(x.val * y.val, x.mod); }; friend pp operator*(const pp& x, const pp&& y) { return pp(x.val * y.val, x.mod); }; friend pp operator*(const pp&& x, const pp&& y) { return pp(x.val * y.val, x.mod); }; template <typename T> friend pp operator*(const pp& x, const T& y) { return pp(x.val * y, x.mod); }; template <typename T> friend pp operator*(const pp&& x, const T& y) { return pp(x.val * y, x.mod); }; template <typename T> friend pp operator*(const pp& x, const T&& y) { return pp(x.val * y, x.mod); }; template <typename T> friend pp operator*(const pp&& x, const T&& y) { return pp(x.val * y, x.mod); }; friend pp operator~(const pp& x) { return x.exp(-1); } friend pp operator~(const pp&& x) { return x.exp(-1); } friend pp operator/(const pp& x, const pp& y) { return x * (~y); }; friend pp operator/(const pp&& x, const pp& y) { return x * (~y); }; friend pp operator/(const pp& x, const pp&& y) { return x * (~y); }; friend pp operator/(const pp&& x, const pp&& y) { return x * (~y); }; template <typename T> friend pp operator/(const pp& x, const T& y) { return x * pp(y, x.mod).inv(); }; template <typename T> friend pp operator/(const pp&& x, const T& y) { return x * pp(y, x.mod).inv(); }; template <typename T> friend pp operator/(const pp& x, const T&& y) { return x * pp(y, x.mod).inv(); }; template <typename T> friend pp operator/(const pp&& x, const T&& y) { return x * pp(y, x.mod).inv(); }; friend pp& operator+=(pp& x, const pp& y) { x.val += y.val; x.recalc(); return x; }; friend pp& operator+=(pp& x, const pp&& y) { x.val += y.val; x.recalc(); return x; }; template <typename T> friend pp& operator+=(pp& x, const T& y) { x.val += y; x.recalc(); return x; }; template <typename T> friend pp& operator+=(pp& x, const T&& y) { x.val += y; x.recalc(); return x; }; friend pp& operator-=(pp& x, const pp& y) { x.val -= y.val; x.recalc(); return x; }; friend pp& operator-=(pp& x, const pp&& y) { x.val -= y.val; x.recalc(); return x; }; template <typename T> friend pp& operator-=(pp& x, const T& y) { x.val -= y; x.recalc(); return x; }; template <typename T> friend pp& operator-=(pp& x, const T&& y) { x.val -= y; x.recalc(); return x; }; friend pp& operator*=(pp& x, const pp& y) { x.val *= y.val; x.recalc(); return x; }; friend pp& operator*=(pp& x, const pp&& y) { x.val *= y.val; x.recalc(); return x; }; template <typename T> friend pp& operator*=(pp& x, const T& y) { x.val *= y; x.recalc(); return x; }; template <typename T> friend pp& operator*=(pp& x, const T&& y) { x.val *= y; x.recalc(); return x; }; friend pp& operator/=(pp& x, const pp& y) { x *= pp(y.val, x.mod).inv(); x.recalc(); return x; }; friend pp& operator/=(pp& x, const pp&& y) { x *= pp(y.val, x.mod).inv(); x.recalc(); return x; }; template <typename T> friend pp& operator/=(pp& x, const T& y) { x *= pp(y, x.mod).inv(); x.recalc(); return x; }; template <typename T> friend pp& operator/=(pp& x, const T&& y) { x *= pp(y, x.mod).inv(); x.recalc(); return x; }; pp exp(ll x) const { if (x == 0) { return pp(1, this->mod); } pp y = *this; if (x > 0) { vl Vec; while (x > 0) { Vec.push_back(x & 1); x >>= 1; } pp ans(1, this->mod); each(ite, Vec) { if (*ite) ans = ans * y; y = y * y; } return ans; } return y.exp(y.mod - 2).exp(-x); }; pp inv() const { return ~(*this); return pp(this->val, this->mod).exp(-1); } friend ostream& operator<<(ostream& os, const pp& x) { if (ignorePPModPrint) { os << "{" << x.val << "}"; } else { os << "{" << x.val << " %" << x.mod << "}"; } return os; }; }; bool pp::ignorePPModPrint = false; class factorial { public: const ll size; vector<pp> vec; /// @brief mod! (operator[] comb) /// @param x max! [0,x] (default 1000000) /// @param y mod (default 998244353) factorial(const ll&& x = 1000000, const ll&& y = 998244353) : size(x + 1) { vec = vector<pp>(x + 1, pp(1, y)); cnt(i, 2, x) vec[i] *= (vec[i - 1] * pp(i, y)); }; /// @brief mod factorial /// @return x! mod pp operator[](const ll& x) const { return vec[x]; }; /// @brief mod factorial /// @return x! mod pp operator[](const ll&& x) const { return vec[x]; }; /// @brief mod combination /// @param n /// @param m /// @return nCm pp comb(const ll n, const ll m) const { return (vec[n] / (vec[m] * vec[n - m])); }; }; class convolution998244353 { int div_lmt; pp zeta; vector<pp> roots; vector<pp> inv_roots; vector<pp> ntt(const vector<pp>& vec, const bool& inverse, const int& sizelog2, int div_cnt = -1) { if (div_cnt == -1) div_cnt = div_lmt; vector<pp> nxt_vec; while (nxt_vec.size() < vec.size()) nxt_vec.push_back(pp(0, zeta.mod)); // nxt_vec.resize(vec.size()); pp zt(1, zeta.mod); if (vec.size() == 1 || div_cnt == 0) { rep(i, nxt_vec.size()) { pp ztij = zt; rep(j, vec.size()) { nxt_vec[i] += vec[j] * ztij; ztij *= zt; } zt *= (inverse ? roots[0] : inv_roots[0]); } return nxt_vec; } vector<pp> vec1(vec.size() / 2); vector<pp> vec2(vec.size() / 2); rep(i, vec.size() / 2) { vec1[i] = vec[2 * i]; vec2[i] = vec[2 * i + 1]; } vector<pp> dft1 = ntt(vec1, inverse, sizelog2 - 1, div_cnt - 1); vector<pp> dft2 = ntt(vec2, inverse, sizelog2 - 1, div_cnt - 1); rep(i, vec.size()) { nxt_vec[i] = dft1[i % dft1.size()] + zt * dft2[i % dft2.size()]; zt *= (inverse ? roots[sizelog2] : inv_roots[sizelog2]); } return nxt_vec; }; public: convolution998244353() : div_lmt(23), zeta(pp(3, 998244353)), roots(vector<pp>(div_lmt + 1, pp(0, 998244353))), inv_roots(vector<pp>(div_lmt + 1, pp(0, 998244353))) { roots[div_lmt] = zeta.exp((zeta.mod - 1) / (1LL << 23)); inv_roots[div_lmt] = roots[div_lmt].inv(); rcnt(i, div_lmt - 1, 0) { roots[i] = roots[i + 1] * roots[i + 1]; inv_roots[i] = inv_roots[i + 1] * inv_roots[i + 1]; } }; vector<pp> conv(vector<pp> vec1, vector<pp> vec2) { int size = 1, sizelog2 = 0; while ((int)(vec1.size() + vec2.size()) > size) { size <<= 1; sizelog2++; } while ((int)vec1.size() < size) vec1.push_back(pp(0, zeta.mod)); while ((int)vec2.size() < size) vec2.push_back(pp(0, zeta.mod)); // vec1.resize(size); // vec2.resize(size); vector<pp> dft1 = ntt(vec1, 1, sizelog2); vector<pp> dft2 = ntt(vec2, 1, sizelog2); vector<pp> dft(size); rep(i, size) dft[i] = dft1[i] * dft2[i]; vector<pp> conv_vec = ntt(dft, 0, sizelog2); rep(i, conv_vec.size()) conv_vec[i] /= size; return conv_vec; } }; }; // namespace zz_mod using namespace zz_mod; namespace zz_prime { class prime { public: static vl sieve; static vl p; static void set(ll N = 1000000) { N = max<ll>(2, N) + 1; sieve = vl(N, 0); p.clear(); sieve[0] = 1; sieve[1] = 1; cnt(i, 2, N - 1) { if (sieve[i] == 0) { p.push_back(i); ll j = i; while (j < N) { if (sieve[j] == 0) sieve[j] = i; j += i; } } } }; static bool isprime(ll x) { if (x <= 1) return false; if (sieve.empty()) set(); if (x < sieve.size()) return (sieve[x] == x); each(ite, p) { if (x < (*ite) * (*ite)) return true; if ((x % (*ite)) == 0) return false; } return true; }; static vxy factor(ll x) { x = max<ll>(1, x); if (sieve.empty()) set(); map<ll, ll> MAP; each(ite, p) { if (x < sieve.size()) break; while ((x % (*ite)) == 0) { MAP[*ite]++; x /= *ite; } } if (x < sieve.size()) { while (x > 1) { MAP[sieve[x]]++; x /= sieve[x]; } } else { MAP[x]++; } vxy fact; each(ite, MAP) fact.push_back(*ite); return fact; }; static vl divisors(const vxy& fact) { vl ans(1, 1); function<void(const ll&, const ll&)> Func = [&fact, &ans, &Func](const ll& I, const ll& Elm) -> void { if (fact.empty()) return; ll Add = 1; if ((I + 1) < fact.size()) { Func(I + 1, Elm); } else { if (Elm != 1) ans.emplace_back(Elm); } cnt(i, 1, fact[I].second) { Add *= fact[I].first; if ((I + 1) < fact.size()) { Func(I + 1, Elm * Add); } else { ans.emplace_back(Elm * Add); } }; }; Func(0, 1); sort(ans.begin(), ans.end()); return ans; }; }; vl prime::p; vl prime::sieve; } // namespace zz_prime using namespace zz_prime; unordered_map<ll, ll> MAP; ///////////////////////////////////////////////// void solve(const ll& N) { auto ITE = MAP.find(N); if (ITE != MAP.end()) { cout << ITE->second << endl; return; } vxy Vec = prime::factor(N); // dbg::zout<1>(N, Vec); ll D = LONG_LONG_MAX; each(ite, Vec) { D = min<ll>(D, ite->second); } each(ite, Vec) { D = __gcd(D, ite->second); } MAP[N] = D; cout << D << endl; }; ///////////////////////////////////////////////// int main() { dbg::unprint = true; prime::set(1000000); ll Q; cin >> Q; vl N(Q); rep(i, Q) cin >> N[i]; rep(i, Q) solve(N[i]); return 0; }