#1195228 (C++17) No.3776 Magic Square of Product

• 問題: No.3776 Magic Square of Product
• ユーザー: tnakao0123
• 提出日時: 2026-10-24 19:01:07
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 49 ms / 2,500 ms
• コード長: 3,038 bytes
• コンパイル時間: 484 ms
• コンパイル使用メモリ: 81,276 KB
• 実行使用メモリ: 9,872 KB
• 最終ジャッジ日時: 2026-10-24 19:01:11
• 合計ジャッジ時間: 3,869 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge6_0

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

ソースコード

/* -*- coding: utf-8 -*-
 *
 * 3776.cc:  No.3776 Magic Square of Product - yukicoder
 */

#include<cstdio>
#include<vector>
#include<algorithm>
#include<utility>

using namespace std;

/* constant */

const int MAX_K = 1000000;
const int MAX_S = 20;
const int MOD = 998244353;

/* typedef */

using vb = vector<bool>;
using vi = vector<int>;
using pii = pair<int,int>;
using vpii = vector<pii>;

template<const int MOD>
struct MI {
  int v;
  MI(): v() {}
  MI(int _v): v(_v % MOD) { if (v < 0) v += MOD; }
  MI(long long _v): v(_v % MOD) { if (v < 0) v += MOD; }

  explicit operator int() const { return v; }
  
  MI operator+(const MI m) const { return MI(v + m.v); }
  MI operator-(const MI m) const { return MI(v + MOD - m.v); }
  MI operator-() const { return MI(MOD - v); }
  MI operator*(const MI m) const { return MI((long long)v * m.v); }

  MI &operator+=(const MI m) { return (*this = *this + m); }
  MI &operator-=(const MI m) { return (*this = *this - m); }
  MI &operator*=(const MI m) { return (*this = *this * m); }

  bool operator==(const MI m) const { return v == m.v; }
  bool operator!=(const MI m) const { return v != m.v; }

  MI pow(int n) const {  // a^n % MOD
    MI pm = 1, a = *this;
    while (n > 0) {
      if (n & 1) pm *= a;
      a *= a;
      n >>= 1;
    }
    return pm;
  }

  MI inv() const { return pow(MOD - 2); }
  MI operator/(const MI m) const { return *this * m.inv(); }
  MI &operator/=(const MI m) { return (*this = *this / m); }
};

using mi = MI<MOD>;

/* global variables */

vb primes;
vi pnums;
int cs[MAX_S + 1];

/* subroutines */

int gen_primes(int maxp) {
  primes.assign(maxp + 1, true);
  primes[0] = primes[1] = false;
  pnums.clear();

  int p;
  for (p = 2; p * p <= maxp; p++)
    if (primes[p]) {
      pnums.push_back(p);
      for (int q = p * p; q <= maxp; q += p) primes[q] = false;
    }
  for (; p <= maxp; p++)
    if (primes[p]) pnums.push_back(p);
  return (int)pnums.size();
}

vpii prime_decomp(int n) {
  vpii pds;

  for (auto pi: pnums) {
    if (pi * pi > n) {
      if (n > 1) pds.push_back(pii(n, 1));
      break;
    }

    if (n % pi == 0) {
      int fi = 0;
      while (n % pi == 0) n /= pi, fi++;
      pds.push_back(pii(pi, fi));
    }
  }
  return pds;
}

int countmagic(int s) {
  int cnt = 0;
  for (int i0 = 0; i0 <= s; i0++)
    for (int i1 = 0; i0 + i1 <= s; i1++) {
      int i2 = s - (i0 + i1);
      for (int i3 = 0; i0 + i3 <= s; i3++) {
	int i6 = s - (i0 + i3);
	int max13 = max(i1, i3);
	for (int i4 = 0; max13 + i4 <= s; i4++) {
	  int i5 = s - (i3 + i4);
	  int i7 = s - (i1 + i4);
	  if (i2 + i5 <= s && i2 + i5 == i6 + i7) cnt++;
	}
      }
    }

  //printf(" countmgic(%d) = %d\n", s, cnt);
  return cnt;
}

/* main */

int main() {
  for (int s = 0; s <= MAX_S; s++) cs[s] = countmagic(s);

  gen_primes(MAX_K);
  
  int tn;
  scanf("%d", &tn);

  while (tn--) {
    int k;
    scanf("%d", &k);

    auto pds = prime_decomp(k);
    mi c = 1;
    for (auto [p, d]: pds) c *= cs[d];

    printf("%d\n", (int)c);
  }

  return 0;
}