#1075743 (C++23) No.3115 One Power One Kill

提出ソース
結果

問題	No.3115 One Power One Kill
コンテスト
ユーザー	rogi52
提出日時	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
権限があれば一括ダウンロードができます
ソースコード

raw source code
#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);
}
yukicoder

結果

ソースコード
