問題一覧 > 通常問題

No.3416 Matchstick Puzzle Extra

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 7
作問者 : tko919 / テスター : 👑 Nachia
お気に入りにしたユーザー ProblemId : 12914 / 自分の提出
問題文最終更新日: 2025-12-22 23:59:54
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2025 (順位表) の他の問題:

Problem Statement

The execution time limit for this problem is set very strictly. The writer's solution (C++) runs in 1165 ms.

You are given a positive integer $N$. How many pairs of positive integers $(H,W)$ satisfy the following condition?
Since the answer can be very large, output it modulo $998244353$.
  • A grid with $H$ rows and $W$ columns can be made using at most $N$ matchsticks. For example, $17$ matchsticks are needed to make a grid with $2$ rows and $3$ columns.

You are given $T$ test cases; answer each of them.

Input

The input is given from Standard Input in the following format. Here, $\mathrm{case}_t\ (1 \leq t \leq T)$ denotes the $t$-th test case.

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$
Each test case is given in the following format.

$N$

Constraints

  • All input values are integers.
  • $1 \leq T \leq 5$
  • $4 \leq N \leq 10^{18}$

Output

Output $T$ lines. The $t$-th line should contain the answer to the $t$-th test case.

Sample

Sample 1
Input
3
10
2025
1000000000000000000
Output
5
5919
223288565

For $N=10$, the pairs satisfying the condition are the $5$ pairs $(H,W)=(1,1),(1,2),(1,3),(2,1),(3,1)$.
Note that you must output the answer modulo $998244353$.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。