結果
問題 |
No.3115 One Power One Kill
|
ユーザー |
|
提出日時 | 2025-04-18 23:55:14 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 83 ms / 2,000 ms |
コード長 | 12,553 bytes |
コンパイル時間 | 4,498 ms |
コンパイル使用メモリ | 313,196 KB |
実行使用メモリ | 25,996 KB |
平均クエリ数 | 2.00 |
最終ジャッジ日時 | 2025-04-18 23:55:22 |
合計ジャッジ時間 | 7,477 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
#line 2 "/Users/korogi/Desktop/cp-cpp/template.hpp" #include <bits/stdc++.h> using namespace std; using i32 = int; using i64 = long long; using i128 = __int128; using u32 = unsigned int; using u64 = unsigned long long; using u128 = unsigned __int128; using f32 = double; using f64 = long double; using f128 = __float128; #define DMP(x) cout << "[" << __LINE__ << "]" << " " << #x << ":" << " " << x << endl; #define FOR1(n) for(int _ = 0 , n_ = (n); _ < n_; _++) #define FOR2(i, n) for(int i = 0 , n_ = (n); i < n_; i++) #define FOR3(i, s, t) for(int i = (s), t_ = (t); i < t_; i++) #define FOR4(i, s, t, d) for(int i = (s), t_ = (t), d_ = (d); i < t_; i += d_) #define OVERLOAD4(a, b, c, d, e, ...) e #define FOR(...) OVERLOAD4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__) #define REV1(n) for(int _ = (n) - 1; _ >= 0 ; _--) #define REV2(i, n) for(int i = (n) - 1; i >= 0 ; i--) #define REV3(i, s, t) for(int i = (t) - 1, s_ = (s); i >= s_; i--) #define REV4(i, s, t, d) for(int i = (t) - 1, s_ = (s), d_ = (d); i >= s_; i -= d_) #define OVERLOAD3(a, b, c, d, ...) d #define REV(...) OVERLOAD4(__VA_ARGS__, REV4, REV3, REV2, REV1)(__VA_ARGS__) #define FOR_SUBSET(T, S) for(int S_ = (S), T = S_; T >= 0; T = (T == 0 ? -1 : (T - 1) & S_)) #define MULTI for(int testcase_ = in(), testcase = 0; testcase < testcase_; testcase++) [&] template < class T > using heap_max = priority_queue< T, vector< T >, less< T > >; template < class T > using heap_min = priority_queue< T, vector< T >, greater< T >>; template < class T, class U > bool chmin(T& a, const U& b) { return a > b ? a = b, 1 : 0; } template < class T, class U > bool chmax(T& a, const U& b) { return a < b ? a = b, 1 : 0; } i64 floor_div(const i64 n, const i64 d) { assert(d != 0); return n / d - ((n ^ d) < 0 && n % d != 0); } i64 ceil_div(const i64 n, const i64 d) { assert(d != 0); return n / d + ((n ^ d) >= 0 && n % d != 0); } template < class T, class F > T bin_search(T ok, T ng, F check) { while(abs(ok - ng) > 1) { T mid = (ok + ng) / 2; (check(mid) ? ok : ng) = mid; } return ok; } template < class T, class F > T bin_search_real(T ok, T ng, F check, int step = 100) { FOR(step) { T mid = (ok + ng) / 2; (check(mid) ? ok : ng) = mid; } return ok; } template < class T, class U > T accum(const vector< U >& a) { return accumulate(a.begin(), a.end(), T(0)); } template < class T > pair< T, int > min(const vector< T >& a) { auto itr = min_element(a.begin(), a.end()); return {*itr, itr - a.begin()}; } template < class T > pair< T, int > max(const vector< T >& a) { auto itr = max_element(a.begin(), a.end()); return {*itr, itr - a.begin()}; } template < class T > void sort(vector< T >& a) { sort(a.begin(), a.end()); } template < class T > void rsort(vector< T >& a) { sort(a.rbegin(), a.rend()); } template < class T > void reverse(vector< T >& a) { reverse(a.begin(), a.end()); } void sort(string& s) { sort(s.begin(), s.end()); } void rsort(string& s) { sort(s.rbegin(), s.rend()); } void reverse(string& s) { reverse(s.begin(), s.end()); } template < class T, class Cmp > void sort(vector< T >& a, Cmp cmp) { sort(a.begin(), a.end(), cmp); } template < class T > int LB(vector< T >& a, T x) { return distance(a.begin(), lower_bound(a.begin(), a.end(), x)); } template < class T > int UB(vector< T >& a, T x) { return distance(a.begin(), upper_bound(a.begin(), a.end(), x)); } template < class T > void unique(vector< T >& a) { sort(a.begin(), a.end()); a.erase(unique(a.begin(), a.end()), a.end()); } vector<int> iota(int n) { vector<int> a(n); iota(a.begin(), a.end(), 0); return a; } istream& operator >> (istream& is, i128& x) { string s; is >> s; int m = (s[0] == '-'); x = 0; FOR(i, m, ssize(s)) x = x * 10 + (s[i] - '0'); if(m) x *= -1; return is; } ostream& operator << (ostream& os, const i128& x) { if(x == 0) return os << '0'; i128 y = x; if(y < 0) { os << '-'; y *= -1; } vector<int> ny; while(y) ny.push_back(y % 10), y /= 10; REV(i, ssize(ny)) os << ny[i]; return os; } namespace scan { struct x0 { template < class T > operator T() { T x; cin >> x; return x; } }; struct x1 { int n; x1(int n) : n(n) {} template < class T > operator vector< T >() { vector< T > a(n); for(T& x : a) cin >> x; return a; } }; struct x2 { int h, w; x2(int h, int w) : h(h), w(w) {} template < class T > operator vector< vector< T > >() { vector m(h, vector< T >(w)); for(vector< T >& a : m) for(T& x : a) cin >> x; return m; } }; struct cppio { cppio() { cin.tie(0); ios::sync_with_stdio(0); } } cppio_instance; } scan::x0 in() { return scan::x0(); } scan::x1 in(int n) { return scan::x1(n); } scan::x2 in(int h, int w) { return scan::x2(h, w); } template < class T > ostream& operator << (ostream& os, const vector< T > a) { const int n = a.size(); FOR(i, n) { os << a[i]; if(i + 1 != n) os << ' '; } return os; } template < class T > int print_n(const vector< T > a) { for(T x : a) cout << x << '\n'; return 0; } int print() { cout << '\n'; return 0; } template < class Head, class... Tail > int print(Head&& h, Tail&&... t) { cout << h; if(sizeof...(Tail)) cout << ' '; return print(forward<Tail>(t)...); } namespace printer { void prec(int n) { cout << fixed << setprecision(n); } void flush() { cout.flush(); } } constexpr pair<int, int> dir4[] = {{-1, 0}, {0, -1}, {+1, 0}, {0, +1}}; vector<int>& operator ++ (vector<int>& a) { for(auto& e : a) e++; return a; } vector<int>& operator -- (vector<int>& a) { for(auto& e : a) e--; return a; } vector<int> operator ++ (vector<int>& a, int) { vector<int> b = a; ++a; return b; } vector<int> operator -- (vector<int>& a, int) { vector<int> b = a; --a; return b; } template < class T > vector<pair< T, int>> RLE(const vector< T >& a) { vector<pair< T, int>> v; for(const T& x : a) { if(not v.empty() and v.back().first == x) v.back().second++; else v.emplace_back(x, 1); } return v; } vector<pair<char, int>> RLE(const string& s) { vector<pair<char, int>> v; for(const char& c : s) { if(not v.empty() and v.back().first == c) v.back().second++; else v.emplace_back(c, 1); } return v; } template < class String, class Same > vector<String> RLE(const String& a, const Same same) { vector<String> v; for(const auto& x : a) { if(not v.empty() and same(v.back().back(), x)) v.back().push_back(x); else v.push_back({x}); } return v; } int YESNO(bool yes) { return print(yes ? "YES" : "NO"); } int YesNo(bool yes) { return print(yes ? "Yes" : "No"); } constexpr i32 INF32 = 1e9; constexpr i64 INF64 = 1e18; #line 2 "/Users/korogi/Desktop/cp-cpp/mod/pow.hpp" u64 modpow64(u64 a, u64 n, u64 mod) { a %= mod; u64 res = 1; for(; n; n >>= 1) { if(n & 1) res = u128(res) * a % mod; a = u128(a) * a % mod; } return res; } u64 modpow(u64 a, u64 n, u64 mod) { a %= mod; u64 res = 1; for(; n; n >>= 1) { if(n & 1) res = res * a % mod; a = a * a % mod; } return res; } #line 3 "/Users/korogi/Desktop/cp-cpp/rnd.hpp" namespace rnd { u32 seed; mt19937 mt; struct gen_seed { gen_seed() { seed = random_device()(); mt = mt19937(seed); } } gen_seed_instance; // [L, R) template < class Int > Int i(Int L, Int R) { assert(L < R); return uniform_int_distribution<Int>(L, R - 1)(mt); } template < class Real > Real r(Real L, Real R) { assert(L <= R); return uniform_real_distribution<Real>(L, R)(mt); } } template < int n, array<u32, n> mod > struct hash_vector { array<u32, n> a; using hvec = hash_vector; hvec& s(array<u32, n> a) { FOR(i, n) this->a[i] = a[i] < mod[i] ? a[i] : a[i] - mod[i]; return *this; } hash_vector(u32 v = 0) { FOR(i, n) a[i] = v % mod[i] + mod[i]; s(a); } hvec operator - () const { return hvec() - *this; } hvec& operator += (const hvec& r) { FOR(i, n) a[i] += r.a[i]; return s(a); } hvec& operator -= (const hvec& r) { FOR(i, n) a[i] += mod[i] - r.a[i]; return s(a); } hvec& operator *= (const hvec& r) { FOR(i, n) a[i] = u64(a[i]) * r.a[i] % mod[i]; return *this; } hvec& operator /= (const hvec& r) { return *this *= inv(r); } hvec operator + (const hvec& r) const { return hvec(*this) += r; } hvec operator - (const hvec& r) const { return hvec(*this) -= r; } hvec operator * (const hvec& r) const { return hvec(*this) *= r; } hvec operator / (const hvec& r) const { return hvec(*this) /= r; } bool operator == (const hvec& r) const { return a == r.a; } bool operator != (const hvec& r) const { return a != r.a; } bool operator < (const hvec& r) const { return a < r.a; } }; template < int n, array<u32, n> mod > hash_vector<n, mod> pow(hash_vector<n, mod> x, u64 m) { hash_vector<n, mod> p(1); for(; m; m >>= 1) { if(m & 1) p *= x; x *= x; } return p; } template < int n, array<u32, n> mod > hash_vector<n, mod> inv(hash_vector<n, mod> x) { hash_vector<n, mod> res; FOR(i, n) { u32 a = x.a[i], b = mod[i], u = 1, v = 0; while(b) { u32 t = a / b; swap(a -= t * b, b); swap(u -= t * v, v); } res[i] = u; } return res; } template < int n, array<u32, n> mod > ostream& operator << (ostream& os, const hash_vector< n, mod >& x) { FOR(i, n) { if(i) os << ' '; os << x.a[i]; } return os; } using hvec1 = hash_vector< 1, array<u32, 1>{999999937} >; using hvec2 = hash_vector< 2, array<u32, 2>{999999937, 1000000007} >; using hvec3 = hash_vector< 3, array<u32, 3>{999999937, 1000000007, 1000000009} >; using hvec4 = hash_vector< 4, array<u32, 4>{999999937, 1000000007, 1000000009, 1000000021} >; #line 4 "/Users/korogi/Desktop/cp-cpp/nt/prime.hpp" // n is prime? judge by witness. bool miller_rabin(u64 n, vector<u64> witness) { if(n == 1) return false; if(n % 2 == 0) return n == 2; u64 d = n - 1; while(d % 2 == 0) d /= 2; for(u64 a : witness) if(a < n) { u64 y = modpow64(a, d, n), t = d; while(t != n - 1 and y != 1 and y != n - 1) { y = u128(y) * y % n; t *= 2; } if(y != n - 1 and t % 2 == 0) return false; } return true; } // n is prime? bool prime_test(u64 n) { if(n < (u64(1) << 32)) return miller_rabin(n, {2, 7, 61}); return miller_rabin(n, {2, 325, 9375, 28178, 450775, 9780504, 1795265022}); } // return non-trivial divisor u64 pollard_rho(u64 n) { if(n % 2 == 0) return 2; if(prime_test(n)) return n; while(true) { u64 R = rnd::i<u64>(2, n), x, y = rnd::i<u64>(2, n), ys, q = 1, g = 1, m = 128; auto f = [&](u64 x) { return (u128(x) * x % n + R) % n; }; for(int r = 1; g == 1; r *= 2) { x = y; FOR(i, r) y = f(y); for(int k = 0; g == 1 and k < r; k += m) { ys = y; for(int i = 0; i < m and i < r - k; i++) { q = u128(q) * ((x - (y = f(y)) + n) % n) % n; } g = gcd(q, n); } } if(g == n) { do { g = gcd((x - (ys = f(ys))), n); } while(g == 1); } if(g != n) return g; } return 0; } // p, p, p, q, q, r, ... // sorted vector<u64> factor(u64 n) { auto dfs = [&](auto&& dfs, u64 n) -> vector<u64> { if(n <= 1) return vector<u64>{}; u64 d = pollard_rho(n); if(d == n) return vector<u64>{n}; vector<u64> L = dfs(dfs, d), R = dfs(dfs, n / d); L.insert(L.end(), R.begin(), R.end()); return L; }; vector<u64> res = dfs(dfs, n); sort(res.begin(), res.end()); return res; } // {p, 3}, {q, 2}, {r, 1}, ... vector<pair<u64, i32>> factor_pair(u64 n) { vector<u64> pf = factor(n); vector<pair<u64, i32>> res; if(pf.empty()) return res; res.push_back({pf[0], 1}); FOR(i, 1, ssize(pf)) { if(res.back().first == pf[i]) res.back().second++; else res.push_back({pf[i], 1}); } return res; } u64 euler_phi(u64 n) { vector<pair<u64,i32>> pf = factor_pair(n); for(auto [p, e] : pf) n -= n / p; return n; } #line 3 "b.cpp" int main() { constexpr i64 P = 1e9 + 7; constexpr i64 A = 100; constexpr i64 B = 132; constexpr i64 L = 100; constexpr i64 R = 100'000; unordered_map<i64, i64> mp; for(i64 X = L; X <= R; X++) { const i64 IN = gcd(X, modpow64(A, B, P)); const i64 OUT = modpow64(X, A, B); if(mp.contains(IN)) { assert(mp[IN] == OUT); } else { mp[IN] = OUT; } } print(A, B); printer::flush(); const i64 K = in(); print(mp[K]); printer::flush(); const int ret = in(); assert(ret == 1); }