結果
| 問題 | No.3776 Magic Square of Product |
| コンテスト | |
| ユーザー |
 edon8618
|
| 提出日時 | 2026-10-23 23:34:31 |
| 言語 | C++23 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 399 ms / 2,500 ms |
| + 983µs | |
| コード長 | 14,073 bytes |
| 記録 | |
| コンパイル時間 | 4,803 ms |
| コンパイル使用メモリ | 388,096 KB |
| 実行使用メモリ | 9,844 KB |
| 最終ジャッジ日時 | 2026-10-23 23:34:54 |
| 合計ジャッジ時間 | 14,185 ms |
|
ジャッジサーバーID （参考情報） |
judge5_0 / judge4_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;
// rep(a,sum+1)rep(b,sum+1)rep(c,sum+1)rep(d,sum+1)cnt+=max(a,d)+max(b,c)<=sum && sum<=a+b+c+d;
// return cnt;
sum++;
return sum*(sum+1)*(sum*sum+sum+2)/8;
}
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;
}
}