#1155789 (C++23) No.8130 プラチナバッハ問題

• 問題: No.8130 プラチナバッハ問題
• ユーザー: jastaway
• 提出日時: 2026-04-01 22:53:01
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 8 ms / 6,000 ms
• コード長: 19,462 bytes
• コンパイル時間: 6,090 ms
• コンパイル使用メモリ: 393,444 KB
• 実行使用メモリ: 399,716 KB
• 最終ジャッジ日時: 2026-04-01 22:53:14
• 合計ジャッジ時間: 7,358 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_1

サブタスク	配点	結果
small	10 %	AC * 12
large	90 %	AC * 18
合計	2.5 * 100% = 250 点

ソースコード

#ifdef _DEBUG
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
template<class T> using gset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
template<class T, class U> using gmap = tree<T,U,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
template<class T, class U> using ghmap = gp_hash_table<T, U>;
// #include <boost/rational.hpp>
// using namespace boost;
// using rat = rational<long long int>;
using mint = modint998244353;
// using mint = modint1000000007;
// using mint = modint;
using ll = long long;
using lll = __int128_t;
using ld = long double;
using ull = uint64_t;
using pll = pair<ll, ll>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;
using vm = vector<mint>;
using vvm = vector<vm>;
using vvvm = vector<vvm>;
using vstr = vector<string>;
#define v(T) vector<T>
#define vv(T) vector<vector<T>>
#define vvv(T) vector<vector<vector<T>>>
#define vvvv(T) vector<vector<vector<vector<T>>>>

template<int M> istream &operator>>(istream &is, static_modint<M> &a){ll tmp; is >> tmp; a = tmp; return is;}
template<int M> ostream &operator<<(ostream &os, const static_modint<M> &a){ os << a.val(); return os; }
template<int M> istream &operator>>(istream &is, dynamic_modint<M> &a){ll tmp; is >> tmp; a = tmp; return is;}
template<int M> ostream &operator<<(ostream &os, const dynamic_modint<M> &a){ os << a.val(); return os; }
string to_string(const __int128_t &a) { if (a == 0) return "0"; string s = ""; __int128_t num = a; bool is_negative = false; if (num < 0) { is_negative = true; num = -num; } while (num > 0) { s += '0' + (num % 10); num /= 10; } if (is_negative) s += '-'; reverse(s.begin(), s.end()); return s; }
istream &operator>>(istream &is, __int128_t &a){ string s; is >> s; a = 0; for(char c : s) { if(isdigit(c)) {a = a*10 + (c - '0'); }  } if(s[0]=='-'){ a *= -1; } return is; }
ostream &operator<<(ostream &os, const __int128_t &a){ os << to_string(a); return os; }
template<class T, class U> istream &operator>>(istream &is, pair<T, U> &p) { is >> p.first >> p.second; return is; }
template<class T, class U> ostream &operator<<(ostream &os, const pair<T, U> &p) { if(&os == &std::cerr) { os << "(" << p.first << ", " << p.second << ")"; } else { os << p.first << " " << p.second; } return os; }
template<class T> istream &operator>>(istream &is, vector<T> &vec){ for(T &e : vec){is >> e;} return is; }
template<class T> ostream &operator<<(ostream &os, const vector<T> &vec) { for(int i = 0; i < (int)vec.size(); i++) { os << vec[i] << (i + 1 != (int)vec.size() ? " " : ""); } return os; }
template<class T> istream &operator>>(istream &is, deque<T> &vec){ for(T &e : vec){is >> e;} return is; }
template<class T> ostream &operator<<(ostream &os, const deque<T> &vec) { for(int i = 0; i < (int)vec.size(); i++) { os << vec[i] << (i + 1 != (int)vec.size() ? " " : ""); } return os; }
template<class T> ostream &operator<<(ostream &os, const set<T> &vec) { for(auto itr = vec.begin(); itr != vec.end(); itr++) { os << (itr != vec.begin() ? " " : "") << (*itr); } return os; }
template<class T> ostream &operator<<(ostream &os, const unordered_set<T> &vec) { for(auto itr = vec.begin(); itr != vec.end(); itr++) { os << (itr != vec.begin() ? " " : "") << (*itr); } return os; }
template<class T, class U> ostream &operator<<(ostream &os, const map<T, U> &vec) { for(auto itr = vec.begin(); itr != vec.end(); itr++) { os << (itr != vec.begin() ? " " : "") << (*itr); } return os; }
template<class T, class U> ostream &operator<<(ostream &os, const unordered_map<T, U> &vec) { for(auto itr = vec.begin(); itr != vec.end(); itr++) { os << (itr != vec.begin() ? " " : "") << (*itr); } return os; }

template <class Tuple, size_t... Is> void read_tuple(istream& is, Tuple& t, index_sequence<Is...>) { ((is >> std::get<Is>(t)), ...); }
template <class... Ts> istream& operator>>(istream& is, tuple<Ts...>& t) { read_tuple(is, t, index_sequence_for<Ts...>{}); return is; }
template <class Tuple, size_t... Is> void print_tuple(ostream& os, const Tuple& t, index_sequence<Is...>) { ((os << (Is == 0 ? "" : (&os == &std::cerr ? ", " : " ")) << std::get<Is>(t)), ...); }
template <class... Ts> ostream& operator<<(ostream& os, const tuple<Ts...>& t) { if(&os == &std::cerr) { os << "("; } print_tuple(os, t, index_sequence_for<Ts...>{}); if(&os == &std::cerr) { os << ")"; } return os; }

#ifdef _DEBUG
template <typename... Args>
void debug_out(Args... args) { ((std::cerr << " " << args), ...); std::cerr << "\n"; }
#define debug(...) do { \
    std::cerr << "[" << #__VA_ARGS__ << "]:"; \
    debug_out(__VA_ARGS__); \
} while(0)
#else
#define debug(...) (void)0
#endif

template <class... T> constexpr auto min (T... a) { return min(initializer_list<common_type_t<T...>>{a...}); }
template <class... T> constexpr auto max (T... a) { return max(initializer_list<common_type_t<T...>>{a...}); }
template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>;
template<class T> T opmin(T x, T y) { return min(x, y); }
template<class T> T einf() { return numeric_limits<T>::max()/2; }
template<class T> T opmax(T x, T y) { return max(x, y); }
template<class T> T eminf() { return numeric_limits<T>::min()/2; }
template<class T> T opsum(T x, T y) { return x + y; }
template<class T> T ezero() { return (T)0; }
template<class T> using minseg = segtree<T, opmin<T>, einf<T>>;
template<class T> using maxseg = segtree<T, opmax<T>, eminf<T>>;
template<class T> using sumseg = segtree<T, opsum<T>, ezero<T>>;
// template<class T> struct v : vector<T> { using vector<T> :: vector; };
// template<class T> struct vv : vector<v<T>> { using vector<v<T>> :: vector; };
// template<class T> struct vvv : vector<vv<T>> { using vector<vv<T>> :: vector; };
template<class T, class U> inline bool chmin(T& a, U b) {if(a > b){a = b; return true;} else {return false;}};
template<class T, class U> inline bool chmax(T& a, U b) {if(a < b){a = b; return true;} else {return false;}};
template<class T> T dist_sq(const pair<T, T> &x, const pair<T, T> &y){return (x.first-y.first)*(x.first-y.first)+(x.second-y.second)*(x.second-y.second);}
template<class T> T cross_product(const pair<T, T> &x, const pair<T, T> &y){return x.first * y.second - x.second * y.first;}
template <typename T> struct Reverser {
    T& t;
    auto begin() const { return std::rbegin(t); }
    auto end() const { return std::rend(t); }
};
template <typename T> Reverser<T> reversed(T& t) { return {t}; }
template <typename T> Reverser<const T> reversed(const T& t) { return {t}; }
// #define rep(i,n) for(ll i = 0; i < (ll)(n); i++)
#define _GET5(_1,_2,_3,_4,NAME,...) NAME
#define _rep1(i, n)  for(long long i=0;i<(long long)(n);i++)
#define _rep2(i,k,n) for(long long i=(long long)(k);i<(long long)(n);i++)
#define _rep3(i,k,n,s) for(long long i=(long long)(k);i<(long long)(n);i+=(s))
#define rep(...) _GET5(__VA_ARGS__, _rep3, _rep2, _rep1)(__VA_ARGS__)
#define _rrep1(i, n)  for(long long i=(long long)(n) - 1;i>=0;i--)
#define _rrep2(i,k,n) for(long long i=(long long)(n)-1;i>=(long long)(k);i--)
#define _rrep3(i,k,n,s) for(long long i=(long long)(n);i>=(long long)(k);i-=(s))
#define rrep(...) _GET5(__VA_ARGS__, _rrep3, _rrep2, _rrep1)(__VA_ARGS__)
#define repr(i,n) for(ll i = (ll)(n) - 1; i >= 0; i--)
#define REP(i, l, r) for(ll i = (ll)l; i <= (ll)(r); i++)
#define REPR(i, l, r) for(ll i = (ll)r; i >= (ll)(l); i--)
const ll inf = (1 << 30);
const ll INF = (1LL << 60);
const vector<pair<ll, ll>> DIJ = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}};
void out(){cout<<'\n';}
template<class T, class... Ts> void out(const T& a, const Ts&... b){ cout<<a; (cout<<... << (cout << ' ', b)); cout << '\n';}
void outf(){cout<<endl;}
template<class T, class... Ts> void outf(const T& a, const Ts&... b){ cout<<a; (cout<<... << (cout << ' ', b)); cout << endl;}
template<class T, class U> void outp(pair<T, U> a){ out((a).first, (a).second); }
template<class T, class U> void outpf(pair<T, U> a){ outf((a).first, (a).second); }
template<class T> void outv(T a){rep(i, (a).size()){ cout << (a)[i] << " "; } cout << endl;}
template<class T> void outvL(T a){rep(i, (a).size()){out((a)[i]);} cout << flush; }
// template<class T> void outvv(T a){rep(i, a.size()){ rep(j, a.at(i).size()){cout << a.at(i).at(j) << " "; } cout << endl; }}
// template<class T> void outvp(T a){rep(i, a.size()){ out2(a.at(i).first, a.at(i).second); }}
void setpre(int a){cout << fixed << setprecision(a);}
#define outN cout << "No\n"
#define outY cout << "Yes\n"
void outYN(bool flag) { cout << (flag ? "Yes\n" : "No\n"); }
#define dame(...) {outf(__VA_ARGS__);return 0;}

template<class... T> void read(T&... a){(cin >> ... >> a);}
#define readll(...) ll __VA_ARGS__; read(__VA_ARGS__)
#define readvll(a, n) vector<ll> a(n); read(a)
#define readvvll(a, n, m) vector<vector<ll>> a(n, vector<ll>(m)); read(a)
#define readvstr(a, n) vector<string> a(n); read(a)
#define readvt(type, a, n) vector<type> a(n); read(a)
#define readvll2(a, b, n) vector<ll> a(n), b(n); for(int lopi = 0; lopi < (int)(n); lopi++) cin >> (a)[lopi] >> (b)[lopi]
#define readvll3(a, b, c, n) vector<ll> a(n), b(n), c(n); for(int lopi = 0; lopi < (int)(n); lopi++) cin >> (a)[lopi] >> (b)[lopi] >> (c)[lopi]
#define readstr(...) string __VA_ARGS__; read(__VA_ARGS__)
#define readundirG(G, N, M) G = vvll(N); rep(lopi, M) {ll a, b; cin >> a >> b; G[a-1].push_back(b-1); G[b-1].push_back(a-1);}
#define readdirG(G, N, M) G = vvll(N); rep(lopi, M) {ll a, b; cin >> a >> b; G[a-1].push_back(b-1);}
#define readundirwghG(G, N, M) G = vv(pll)(N); rep(lopi, M) {ll a, b, c; cin >> a >> b >> c; G[a-1].emplace_back(b-1,c); G[b-1].emplace_back(a-1, c);}
#define readdirwghG(G, N, M) G = vv(pll)(N); rep(lopi, M) {ll a, b, c; cin >> a >> b >> c; G[a-1].emplace_back(b-1, c);}

#define All(a) (a).begin(), (a).end()
#define all(a) begin(a), end(a)
template<class T> inline void sortr(T& a){ sort((a).rbegin(), (a).rend()); }
template<class T> inline vector<int> argsort(T V, bool rev = false){vector<int> res(V.size()); iota(res.begin(), res.end(), 0); sort(res.begin(), res.end(), [&](int x, int y){if(!rev){return V[x] < V[y];}else{return V[x] > V[y];}}); return res;}
template<class T, class U> inline void sort_by_idx(T& V, vector<U>& I){assert(V.size() == I.size()); T tmpv = V; for(int loopi = 0; loopi < (int)I.size(); loopi++){V[loopi] = tmpv[I.at(loopi)];}}
template<class T, class U> inline void sortp(vector<T>& v1, vector<U>& v2, bool rev1 = false, int rev2 = false){assert(v1.size() == v2.size()); vector<int> I(v1.size()); iota(I.begin(), I.end(), 0); sort(I.begin(), I.end(), [&](const int x, const int y){if(v1[x] != v1[y]){return (bool)(rev1 ^ (v1[x] < v1[y]));}else{if(v2[x]==v2[y]){return false;} return (bool)(rev2 ^ (v2[x] < v2[y]));}}); sort_by_idx(v1, I); sort_by_idx(v2, I);}
template<class T> T POW(T x, ll n) {T ret = 1; while(n > 0){if(n & 1) ret *= x; x *= x; n >>= 1;} return ret;}
ll powll(ll x, ll n){ll ret = 1; while(n > 0){if(n & 1) ret *= x; x *= x; n >>= 1;} return ret;}
ll modpow(ll a,ll b,ll modd){ll res=1;a%=modd;while(b){if(b&1)res=res*a%modd;a=a*a%modd;b>>=1;}return res;}
ll sqrtll(ll a){assert(a >= 0); ll r = (ll)sqrtl((ld)a)-1; while(r < 0 || (r+1)*(r+1) <= a) r++; return r;}
ll cbrtll(ll a){assert(a >= 0); ll r = (ll)cbrtl((ld)a)-1; while(r < 0 || (r+1)*(r+1)*(r+1) <= a) r++; return r;}
ll modinv(ll a, ll b){assert(a); if(a == 1) return 1; if(b == 1) return 0; ll ret = (1ll-b*modinv(b%a, a))/a; ret %= b; if(ret < 0) ret += b; return ret;}
inline bool inLR(ll x, ll L, ll R){ return (L <= x && x < R); }
inline bool inRect(ll pos_x, ll pos_y, ll rect_H, ll rect_W, ll rect_h = 0, ll rect_w = 0){ return (rect_h <= pos_x && pos_x < rect_H && rect_w <= pos_y && pos_y < rect_W); }

template<class T> vector<T> &operator++(vector<T>& v){for(T& x : v) x++; return v;}
template<class T> vector<T> &operator--(vector<T>& v){for(T& x : v) x--; return v;}
template<class T> vector<T> operator++(vector<T>& v, signed){auto res = v; for(T& x : v) x++; return res;}
template<class T> vector<T> operator--(vector<T>& v, signed){auto res = v; for(T& x : v) x--; return res;}
template<class T> vector<T> operator+=(vector<T>& v, const vector<T>& w){if(v.size() < w.size()) v.resize(w.size()); for(int i = 0; i < (int)w.size(); i++) v[i] += w[i]; return v;}
template<class T> vector<T> operator-=(vector<T>& v, const vector<T>& w){if(v.size() < w.size()) v.resize(w.size()); for(int i = 0; i < (int)w.size(); i++) v[i] -= w[i]; return v;}
template<class T> vector<T> operator*=(vector<T>& v, const vector<T>& w){if(v.size() < w.size()) v.resize(w.size()); for(int i = 0; i < (int)w.size(); i++) v[i] *= w[i]; return v;}
template<class T> vector<T> operator/=(vector<T>& v, const vector<T>& w){if(v.size() < w.size()) v.resize(w.size()); for(int i = 0; i < (int)w.size(); i++) v[i] /= w[i]; return v;}
template<class T> vector<T> operator+(vector<T> v, const vector<T>& w){return (v += w);}
template<class T> vector<T> operator-(vector<T> v, const vector<T>& w){return (v -= w);}
template<class T> vector<T> operator*(vector<T> v, const vector<T>& w){return (v *= w);}
template<class T> vector<T> operator/(vector<T> v, const vector<T>& w){return (v /= w);}
template<class T> vector<T> operator*=(vector<T>& v, T w){for(T& x : v) x*=w; return v;}
template<class T> vector<T> operator/=(vector<T>& v, T w){for(T& x : v) x/=w; return v;}
template<class T> vector<T> operator*(vector<T> v, T x){return (v *= x);}
template<class T> vector<T> operator/(vector<T> v, T x){return (v /= x);}

template<class S, class T> pair<S,T> operator+=(pair<S,T>& p, const pair<S,T>& q){p.fi+=q.fi, p.se+=q.se; return p;}
template<class S, class T> pair<S,T> operator+(pair<S,T> p, const pair<S,T>& q){return (p += q);}
template<class S, class T> pair<S,T> operator-=(pair<S,T>& p, const pair<S,T>& q){p.fi-=q.fi, p.se-=q.se; return p;}
template<class S, class T> pair<S,T> operator-(pair<S,T> p, const pair<S,T>& q){return (p -= q);}

template<class T> size_t HashCombine(const size_t seed,const T &v){ return seed^(std::hash<T>()(v)+0x9e3779b9+(seed<<6)+(seed>>2)); }
template<class T,class S> struct std::hash<std::pair<T,S>>{ size_t operator()(const std::pair<T,S> &keyval) const noexcept { return HashCombine(std::hash<T>()(keyval.first), keyval.second); } };
template<class T> struct std::hash<std::vector<T>>{ size_t operator()(const std::vector<T> &keyval) const noexcept { size_t s=0; for (auto&& v: keyval) s=HashCombine(s,v); return s; } };
template<int N> struct HashTupleCore{ template<class Tuple> size_t operator()(const Tuple &keyval) const noexcept{ size_t s=HashTupleCore<N-1>()(keyval); return HashCombine(s,std::get<N-1>(keyval)); } };
template <> struct HashTupleCore<0>{ template<class Tuple> size_t operator()(const Tuple &keyval) const noexcept{ return 0; } };
template<class... Args> struct std::hash<std::tuple<Args...>>{ size_t operator()(const tuple<Args...> &keyval) const noexcept { return HashTupleCore<tuple_size<tuple<Args...>>::value>()(keyval); } };

ll bigpow(ll x, ll n, ll mod)
{
    __int128_t y = x;
    __int128_t ret = 1;
    y %= mod;
    while(n > 0)
    {
        if(n & 1) ret *= y;
        ret %= mod;
        y = (y * y) % mod;
        n >>= 1;
    }
    return (ll)(ret % mod);
}

bool is_prime(ll n)
{
    if(n == 2) return true;
    if(n == 1 || n % 2 == 0) return false;

    ll m = n - 1;
    ll s = 0;
    while((m & 1) == 0)
    {
        m >>= 1;
        s++;
    }
    ll d = m;
    m = n - 1;
    vector<ll> test_numbers = {2LL, 325LL, 9375LL, 28178LL, 450775LL, 9780504LL, 1795265022LL};
    for(ll a : test_numbers)
    {
        if(a % n == 0) continue;
        ll x = bigpow(a, d, n);
        ll r = 0;
        if(x == 1) continue;
        while(x != m)
        {
            x = bigpow(x, 2, n);
            r += 1;
            if(x == 1 || r == s) return false;
        }
    }
    return true;
}

ll find_primefactor(ll n)
{
    if(n % 2 == 0) return 2;
    for(ll c = 1; c < n; c++)
    {
        function<ll(ll,ll, ll)> f = [](ll a, ll cst, ll md){return (bigpow(a, 2, md) + cst) % md;};
        ll x = 0, y = 0;
        ll g = 1;
        while(g == 1)
        {
            x = f(x, c, n);
            y = f(f(y, c, n), c, n);
            g = gcd(abs(x - y), n);
        }
        if(g == n) continue;
        if(is_prime(g)) return g;
        else if(is_prime(n/g)) return n/g;
        else return find_primefactor(g);
    }
    return n;
}

vector<pair<ll, ll>> prime_factorization(ll n)
{
    vector<pair<ll, ll>> res;
    while(n > 1 && !is_prime(n))
    {
        ll p = find_primefactor(n);
        ll e = 0;
        while(n % p == 0)
        {
            e++;
            n /= p;
        }
        res.push_back({p, e});
    }
    if(n > 1) res.push_back({n, 1});
    sort(res.begin(), res.end());
    return res;
}

vector<long long> Primes(ll MX)
{
    vector<long long> P;
    vector<long long> mnPf(MX + 1, -1);
    for(long long d = 2; d <= MX; d++) {
        if(mnPf[d] == -1)
        {
            mnPf[d] = d;
            P.emplace_back(d);
        }
        for(auto p : P) {
            if(p * d > MX || p > mnPf[d]) break;
            mnPf[p * d] = p;
        }
    }
    return P;
}

std::vector<bool> sieve(intmax_t L, intmax_t R) {
    int n = sqrt(R)+1;  // 念のため多めに
    std::vector<bool> aux(n, true);  // 小さい篩
    std::vector<bool> res(R-L, true);  // 大きい篩
    vector<long long> P;
    for (intmax_t i = 2; i*i < n; ++i) {
        if (!aux[i]) continue;
        for (intmax_t j = i*i; j < R; j += i) aux[j] = false;
        for (intmax_t j = std::max(i, (L+i-1)/i)*i; j < R; j += i) res[j] = false;
    }
    return res;
}

template<class T> vector<T> fast_zeta(const vector<T> &f) {
    int N = f.size();
    vector<T> ret = f;
    // エラトステネスの篩を用いて素数を列挙
    auto P = Primes(N);
    
    // 各素数 p 軸に対して
    // 大きい座標 (k * p) から小さい座標 (k) へと足し込む
    for(auto p : P) {
        
        // 座標が大きい方を起点として累積和をとる
        for (int k = (N - 1) / p; k >= 1; --k) {
            ret[k] += ret[k * p];
        }
    }
    return ret;
}

template<class T> vector<T> fast_mobius(vector<T> &F) {
    int N = F.size();
    vector<T> ret = F;
    // エラトステネスの篩を用いて素数を列挙
    auto P = Primes(N);
    
    // 各素数 p 軸に対して
    // 小さい座標 (k) から大きい座標 (k * p) を引いていく
    for(auto p : P) {
        // 座標が小さい方を起点として差分をとる
        for (int k = 1; k * p < N; ++k) {
            ret[k] -= ret[k * p];
        }
    }
    return ret;
}

int main()
{
    std::cin.tie(nullptr), std::ios_base::sync_with_stdio(false);
    // ll MX = 100000000000000LL;
    // ll MX_P = 100000000LL;
    // auto P = Primes(20);
    // ll M = P.size();
    // set<ll> ans;
    // rep(bit, 1LL << M)
    // {
    //     ll tmp = 0;
    //     rep(i, M) if((bit >> i) & 1) tmp += P[i];
    //     ans.insert(tmp);
    // }
    // out(ans);
    readll(T);
    while(T--)
    {
        readll(N);
        if(N == 1 || N == 4 || N == 6) outN;
        else outY;
    }
}