結果

問題 No.3776 Magic Square of Product
コンテスト
ユーザー Rapca1256
提出日時 2026-07-28 20:23:32
言語 Python3
(3.15.0 + numpy 2.5.4 + scipy 1.18.1 + ACL)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
TLE  
実行時間 -
コード長 3,005 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 54 ms
コンパイル使用メモリ 14,976 KB
実行使用メモリ 10,624 KB
最終ジャッジ日時 2026-10-23 20:51:49
合計ジャッジ時間 13,641 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample TLE * 1
other -- * 25
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
from collections import Counter

# 再帰回数上限
sys.setrecursionlimit(10**9)

# よくあるmod
#MOD = 1000000007
MOD = 998244353

class Factorizer:
    def __init__(self, MAX_VALUE):
        # 0と1は便宜上そのままにするが、基本は自分の値で初期化
        self.min_prime = list(range(MAX_VALUE + 1))
        
        # エラトステネスの篩の要領で最小素因数を埋める
        for p in range(2, int(MAX_VALUE**0.5) + 1):
            if self.min_prime[p] == p:  # pが素数の場合
                # p*p から MAX_VALUE まで p 飛ばしで更新
                # すでに自分より小さい素数で更新されているものは上書きしない
                for i in range(p * p, MAX_VALUE + 1, p):
                    if self.min_prime[i] == i:
                        self.min_prime[i] = p

    def factorize(self, n):
        # 高速素因数分解 (O(log n))
        c = Counter()
        while n > 1:
            p = self.min_prime[n]
            c[p] += 1
            n //= p
        
        # c.items() は辞書の view なので、必要に応じてソートして返す
        return sorted(c.items())
    
MAX = 21
TABLE = [0] * MAX
for k in range(MAX):
    for a in range(MAX):
        for b in range(MAX):
            for c in range(MAX):
                for d in range(MAX):
                    state = [[0] * 3 for _ in range(3)]
                    state[0][0] = a
                    state[0][1] = b
                    state[1][0] = c
                    state[1][1] = d

                    state[0][2] = k - state[0][0] - state[0][1]
                    state[2][0] = k - state[0][0] - state[1][0]

                    state[1][2] = k - state[1][0] - state[1][1]
                    state[2][1] = k - state[0][1] - state[1][1]

                    state[2][2] = k - state[0][2] - state[1][2]

                    for y in range(3):
                        s = 0
                        for x in range(3):
                            if state[y][x] < 0: break
                            s += state[y][x]
                        else:
                            if s != k: break
                            continue
                        break
                    else:
                        for x in range(3):
                            s = 0
                            for y in range(3):
                                if state[y][x] < 0: break
                                s += state[y][x]
                            else:
                                if s != k: break
                                continue
                            break
                        else:
                            TABLE[k] += 1
fc = Factorizer(10**6+5)
def solve():
    # 解答ここから
    K = int(input())
    f = fc.factorize(K)
    ans = 1
    for _, e in f:
        ans = (ans * TABLE[e]) % MOD
    print(ans)
if __name__ == '__main__':
    T = int(input())
    for _ in range(T):
        solve()
0