#1194697 (C++23) No.3776 Magic Square of Product

• 問題: No.3776 Magic Square of Product
• ユーザー: edon8618
• 提出日時: 2026-10-23 22:41:49
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 423 ms / 2,500 ms
• コード長: 14,243 bytes
• コンパイル時間: 5,454 ms
• コンパイル使用メモリ: 388,284 KB
• 実行使用メモリ: 9,908 KB
• 最終ジャッジ日時: 2026-10-23 22:42:05
• 合計ジャッジ時間: 15,583 ms
• ジャッジサーバーID （参考情報）: judge6_0 / judge5_0

ファイルパターン	結果
sample	AC * 1
other	AC * 25

ソースコード

// https://github.com/edon8618/mylib

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2")

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;



// #include <boost/multiprecision/cpp_int.hpp>
// using namespace boost::multiprecision;

#define ll long long
#define ld long double
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define vi vector<int>
#define vl vector<ll>
#define vd vector<double>
// #define vb vector<bool>
#define vs vector<string>
#define vc vector<char>
#define ull unsigned long long
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

template<class T, class U>
inline bool chmax(T &a, const U &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T, class U>
inline bool chmin(T &a, const U &b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}


// #define ll int
// #define ll int128_t
// #define ll int256_t
// #define ll cpp_int


constexpr ll inf = (1ll << 60);
// constexpr ll inf = (1 << 30);
// const double PI=3.1415926535897932384626433832795028841971;

uint32_t xor_x = 123456789, xor_y = 362436069, xor_z = 521288629, xor_w = 88675123;
inline uint32_t xor_next() {
    uint32_t t = xor_x ^ (xor_x << 11);
    xor_x = xor_y; xor_y = xor_z; xor_z = xor_w;
    return xor_w = (xor_w ^ (xor_w >> 19)) ^ (t ^ (t >> 8));
}
inline int rnd(int max_val) { return xor_next() % max_val; }


struct Timer {
    std::chrono::steady_clock::time_point start_time;

    Timer() {
        reset();
    }

    // 測定の起点リセット用
    void reset() {
        start_time = std::chrono::steady_clock::now();
    }

    // スタートからの経過時間をミリ秒(msec)で返す
    long long get_ms() const {
        auto now = std::chrono::steady_clock::now();
        return std::chrono::duration_cast<std::chrono::milliseconds>(now - start_time).count();
    }
};

struct I128Hash {
    size_t operator()(__int128_t a) const {
        uint64_t x = (uint64_t)a ^ (uint64_t)((__uint128_t)a>>64);
        x ^= x >> 30; x *= 0xbf58476d1ce4e5b9ULL;
        x ^= x >> 27; x *= 0x94d049bb133111ebULL;
        return x ^ (x >> 31);
    }
};



// vl fact;
// ll kai(ll n){
//     fact.resize(n,1);
//     rep(i,n-1)fact[i+1]=fact[i]*(i+1);
// }

// using mint = ld;
using mint = modint998244353;//static_modint<998244353>
// using mint = modint1000000007;//static_modint<1000000007>
// using mint = static_modint<922267487>;   // 多分落とされにくい NOT ntt-friendly
// using mint = static_modint<469762049>;   // ntt-friendly
// using mint = static_modint<167772161>;   // ntt-friendly
// using mint = modint;//mint::set_mod(mod);

// ll const mod=1000000007ll;
// ll const mod=998244353ll;
// ll modrui(ll a,ll b,ll mod){
//     a%=mod;
//     if(b==0)return 1;
//     if(b%2==1) return a*modrui(a*a%mod,b/2,mod)%mod;
//     return modrui(a*a%mod,b/2,mod)%mod;
// }

// void incr(vl &v,ll n){//　n進法
//     ll k=v.size();
//     v[k-1]++;
//     ll now=k-1;
//     while (v[now]>=n)
//     {
//         v[now]=0;
//         if(now==0)break;
//         v[now-1]++;
//         now--;
//     }
//     return;
// }

// vector<mint> fact,invf;
// void init_modfact(ll sz){
//     fact.resize(sz);
//     invf.resize(sz);
//     fact[0]=1;
//     rep(i,sz-1){
//         fact[i+1]=fact[i]*(i+1);
//     }
//     invf[sz-1]=1/fact[sz-1];
//     for(ll i=sz-2; i>=0; i--){
//         invf[i]=invf[i+1]*(i+1);
//     }
// }
// mint choose(ll n,ll r){
//     if(n<r || r<0 || n<0)return 0;
//     return fact[n]*invf[r]*invf[n-r];
// }

// vector<mint> modpow,invpow;
// void init_modpow(ll x,ll sz){
//     mint inv=1/mint(x);
//     modpow.assign(sz,1);
//     invpow.assign(sz,1);
//     rep(i,sz-1){
//         modpow[i+1]=modpow[i]*x;
//         invpow[i+1]=invpow[i]*inv;
//     }
// }
// long long phi(long long n) {// O(sqrt(n))
//     long long res = n;
//     for (long long i = 2; i * i <= n; i++) {
//         if (n % i == 0) {
//             res -= res / i;
//             while (n % i == 0) n /= i;
//         }
//     }
//     if (n > 1) res -= res / n;
//     return res;
// }





/*
============================================================
Number Theory Utility
============================================================

[素数判定]
bool nt::is_prime(u64 n);

[mod乗算]
u64 nt::mul_mod(u64 a, u64 b, u64 mod);

[mod累乗]
u64 nt::pow_mod(u64 a, u64 e, u64 mod);
    a^e % mod

[素因数分解]
vector<u64> nt::factor(u64 n);
        nt::factor(12)
        -> {2, 2, 3}

[素因数分解 + 指数]
vector<pair<u64,int>> nt::factor_count(u64 n);
        nt::factor_count(12)
        -> {{2,2}, {3,1}}

[相異なる素因数]
vector<u64> nt::distinct_prime_factors(u64 n);
        nt::distinct_prime_factors(12)
        -> {2,3}

[原始根判定]
bool nt::is_primitive_root(u64 g, u64 p);
    p は素数であること。
    g が mod p の原始根なら true。

[原始根判定 / p-1の素因数既知版]
bool nt::is_primitive_root(
    u64 g,
    u64 p,
    const vector<u64>& pf
);
    pf は p-1 の相異なる素因数。(nt::distinct_prime_factors)
    同じ p で何度も判定するときはこちらを使う。

[原始根探索]
u64 nt::primitive_root(u64 p);

    p は素数であること。
    mod p の原始根を1つ返す。
------------------------------------------------------------
注意
------------------------------------------------------------
・ライブラリ内部は uint64_t 前提。
・long long の非負値ならそのまま渡してよい。
・負の long long を渡すと uint64_t に変換されて壊れる。
・is_primitive_root / primitive_root の p は素数であること。
・factor は Pollard Rho + Miller-Rabin。
・is_prime は 64bit 全域で deterministic。
============================================================
*/

namespace nt {

using u64 = uint64_t;
using u128 = __uint128_t;

// ============================================================
// modular arithmetic
// ============================================================

inline u64 mul_mod(u64 a, u64 b, u64 mod) {
    return (u128)a * b % mod;
}

u64 pow_mod(u64 a, u64 e, u64 mod) {
    assert(mod > 0);
    u64 r = 1 % mod;

    while (e) {
        if (e & 1) {
            r = mul_mod(r, a, mod);
        }

        a = mul_mod(a, a, mod);
        e >>= 1;
    }

    return r;
}


// ============================================================
// deterministic Miller-Rabin for uint64_t
// ============================================================

bool is_prime(u64 n) {
    if (n < 2) return false;

    static constexpr u64 small_primes[] = {
        2ULL, 3ULL, 5ULL, 7ULL, 11ULL, 13ULL,
        17ULL, 19ULL, 23ULL, 29ULL, 31ULL, 37ULL
    };

    for (u64 p : small_primes) {
        if (n % p == 0) {
            return n == p;
        }
    }

    u64 d = n - 1;
    int s = 0;

    while ((d & 1) == 0) {
        d >>= 1;
        ++s;
    }

    auto witness = [&](u64 a) -> bool {
        if (a % n == 0) return false;

        u64 x = pow_mod(a, d, n);

        if (x == 1 || x == n - 1) {
            return false;
        }

        for (int r = 1; r < s; ++r) {
            x = mul_mod(x, x, n);

            if (x == n - 1) {
                return false;
            }
        }

        return true;
    };

    // Deterministic for all uint64_t values.
    static constexpr u64 bases[] = {
        2ULL,
        325ULL,
        9375ULL,
        28178ULL,
        450775ULL,
        9780504ULL,
        1795265022ULL
    };

    for (u64 a : bases) {
        if (witness(a)) {
            return false;
        }
    }

    return true;
}


// ============================================================
// splitmix64 RNG
// ============================================================

struct SplitMix64 {
    u64 x;

    explicit SplitMix64(
        u64 seed = chrono::steady_clock::now()
                       .time_since_epoch()
                       .count()
    ) : x(seed) {}

    u64 operator()() {
        u64 z = (
            x += 0x9e3779b97f4a7c15ULL
        );

        z = (
            z ^ (z >> 30)
        ) * 0xbf58476d1ce4e5b9ULL;

        z = (
            z ^ (z >> 27)
        ) * 0x94d049bb133111ebULL;

        return z ^ (z >> 31);
    }

    u64 range(u64 l, u64 r) {
        return l + (*this)() % (r - l + 1);
    }
};

static SplitMix64 rng;


// ============================================================
// Pollard Rho (Brent)
// ============================================================

u64 pollard_rho(u64 n) {
    if (n % 2 == 0) return 2;
    if (n % 3 == 0) return 3;
    if (n % 5 == 0) return 5;

    constexpr u64 BATCH = 128;

    while (true) {
        u64 y = rng.range(1, n - 1);
        u64 c = rng.range(1, n - 1);

        auto f = [&](u64 x) -> u64 {
            return (
                mul_mod(x, x, n) + c
            ) % n;
        };

        u64 g = 1;
        u64 r = 1;
        u64 q = 1;

        u64 x = 0;
        u64 ys = 0;

        while (g == 1) {
            x = y;

            for (u64 i = 0; i < r; ++i) {
                y = f(y);
            }

            for (
                u64 k = 0;
                k < r && g == 1;
                k += BATCH
            ) {
                ys = y;
                q = 1;

                u64 lim = min(
                    BATCH,
                    r - k
                );

                for (u64 i = 0; i < lim; ++i) {
                    y = f(y);

                    u64 diff = (
                        x > y
                        ? x - y
                        : y - x
                    );

                    q = mul_mod(
                        q,
                        diff,
                        n
                    );
                }

                g = gcd(q, n);
            }

            r <<= 1;
        }

        // Batch gcd returned n itself.
        if (g == n) {
            do {
                ys = f(ys);

                u64 diff = (
                    x > ys
                    ? x - ys
                    : ys - x
                );

                g = gcd(
                    diff,
                    n
                );

            } while (g == 1);
        }

        if (g != n) {
            return g;
        }
    }
}


// ============================================================
// factorization
// ============================================================

void factor_rec(
    u64 n,
    vector<u64>& res
) {
    if (n == 1) {
        return;
    }

    if (is_prime(n)) {
        res.push_back(n);
        return;
    }

    u64 d = pollard_rho(n);

    factor_rec(d, res);
    factor_rec(n / d, res);
}


// 重複込み・昇順
vector<u64> factor(u64 n) {
    vector<u64> res;

    if (n <= 1) {
        return res;
    }

    factor_rec(n, res);

    sort(
        res.begin(),
        res.end()
    );

    return res;
}


// (prime, exponent)
vector<pair<u64, int>> factor_count(
    u64 n
) {
    vector<u64> fs = factor(n);

    vector<pair<u64, int>> res;

    for (u64 p : fs) {
        if (
            res.empty() ||
            res.back().first != p
        ) {
            res.push_back({
                p,
                1
            });
        }
        else {
            ++res.back().second;
        }
    }

    return res;
}


// 相異なる素因数のみ
vector<u64> distinct_prime_factors(
    u64 n
) {
    vector<u64> fs = factor(n);

    fs.erase(
        unique(
            fs.begin(),
            fs.end()
        ),
        fs.end()
    );

    return fs;
}


// ============================================================
// primitive root
// ============================================================

// p must be prime.
// pf = distinct prime factors of p-1.
bool is_primitive_root(
    u64 g,
    u64 p,
    const vector<u64>& pf
) {
    if (p == 2) {
        return g % 2 == 1;
    }

    if (g == 0 || g >= p) {
        return false;
    }

    for (u64 q : pf) {
        if (
            pow_mod(
                g,
                (p - 1) / q,
                p
            ) == 1
        ) {
            return false;
        }
    }

    return true;
}


// p must be prime.
// Factorizes p-1 internally.
bool is_primitive_root(
    u64 g,
    u64 p
) {
    auto pf =
        distinct_prime_factors(
            p - 1
        );

    return is_primitive_root(
        g,
        p,
        pf
    );
}


// p must be prime.
u64 primitive_root(u64 p) {
    if (p == 2) {
        return 1;
    }

    auto pf =
        distinct_prime_factors(
            p - 1
        );

    for (u64 g = 2;; ++g) {
        if (
            is_primitive_root(
                g,
                p,
                pf
            )
        ) {
            return g;
        }
    }
}

} // namespace nt



bool check(array<array<ll,3>,3> &ar,ll sum){
    ll a=ar[0][0],b=ar[0][1];
    ll c=ar[1][0],d=ar[1][1];
    return max({a+b,a+c,b+d,c+d})<=sum && a+b+c+d>=sum;
}

mint make(ll sum){
    mint cnt=0;
    array<array<ll,3>,3> ar;
    for(ar[0][0]=0;ar[0][0]<=sum;ar[0][0]++){
        for(ar[0][1]=0;ar[0][1]<=sum;ar[0][1]++){
            for(ar[1][0]=0;ar[1][0]<=sum;ar[1][0]++){
                for(ar[1][1]=0;ar[1][1]<=sum;ar[1][1]++){
                    if(check(ar,sum))cnt++;
                }
            }
        }
    }
    return cnt;
}

void solve(){
    vector<mint> v(30);
    rep(i,30){
        v[i]=make(i);
        // cerr << v[i].val() << endl;
    }
    // return;

    ll t;
    cin >> t;
    while(t--){
        ll k;
        cin>> k;

        auto pe=nt::factor_count(k);
        mint ans=1;
        for(auto [p,e]:pe)ans*=v[e];
        cout << ans.val() << endl;
    }
}



int main(){
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);


    // ll mx=12345678;
    // vc fl(mx+1,0);
    // for(ll d=2;d<=mx;d++){
    //     if(fl[d])continue;
    //     ll x=d;
    //     ps.push_back(x);
    //     while(x<=mx){
    //         fl[x]=1;
    //         x+=d;
    //     }
    // }


    ll t = 1;
    // cin >> t;
    while (t--){
        solve();
        cout << flush;
    }
}