No.3416 マッチ棒パズル Extra
レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 5
作問者 :
tko919
/ テスター :
Nachia
タグ : / 解いたユーザー数 5
作問者 :
tko919
/ テスター :
Nachia
問題文最終更新日: 2025-12-22 23:59:54
コンテストの他の問題:
問題文
この問題の実行時間制限は非常に厳しく設定されています。Writer 解（C++）は 1165 ms で動作します。正整数 $N$ が与えられます。正整数の組 $(H,W)$ であって、以下の条件を満たすものは何通りありますか？
ただし、答えは非常に大きくなる場合があるので、 $998244353$ で割った余りを答えてください。
- $N$ 本以下のマッチ棒を用いて、 $H$ 行 $W$ 列のグリッドを作ることができる。例えば、$2$ 行 $3$ 列のグリッドを作るには $17$ 本のマッチ棒が必要である。
$T$ 個のテストケースが与えられるので、それぞれについて答えてください。
入力
入力は以下の形式で標準入力から与えられます。ここで $\mathrm{case}_t\ (1 \leq t \leq T)$ は $t$ 番目のテストケースを表します。
$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$
各テストケースは以下の形式で与えられます。
$N$
制約
- 入力はすべて整数
- $1 \leq T \leq 5$
- $4 \leq N \leq 10^{18}$
出力
$T$ 行出力してください。$t$ 行目には $t$ 番目のテストケースについての答えを出力してください。
サンプル
サンプル1
入力
3 10 2025 1000000000000000000
出力
5 5919 223288565
$N=10$ のとき、条件を満たす組は $(H,W)=(1,1),(1,2),(1,3),(2,1),(3,1)$ の $5$ つです。
$998244353$ で割った余りを出力することに注意してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。