No.3310 mod998
タグ : / 解いたユーザー数 36
作問者 : 👑
ArcAki
/ テスター :
chiaoi
ストーリー
あー、はい、いつもの $\mod998$ …じゃない？！
問題文
$T$ 個のテストケースが与えられます。各テストケースについて以下の問題を解いて下さい。
非負整数 $N$ と 正整数 $M$ が与えられます。$M$ 個の非負整数 $K_1,\ K_2,\ \cdots\ K_M$ が与えられるので各 $K_j$ について
$(\sum_{i=0}^{K_j}{{N}^i)} \mod 998$ を求めてください。
ただしこの問題では $0^0 = 1$ とします。
入力
入力は以下の形式で与えられます。$T$ $testcase_1$ $\vdots$ $testcase_T$
ここで $testcase_i$ は $i$ 番目のテストケースを表しそれぞれ以下の形式で与えられます。
$N_i\ M_i$
${K_i}_1$
$\vdots$
${K_i}_{M_i}$
- 入力は全て整数である。
- $1 ≤ T ≤ 50$
- 各テストケースについて以下を満たす。
- $0 ≤ N_i < 998$
- $1 ≤ M_i ≤ 10^3$
- $0 ≤ {K_i}_j < 10^{10^{5}}$
- テストケース内の ${K_i}_j$ の $10$ 進数表記での桁数の総和は $10^5$ 以下である。
出力
各テストケースの答えを順に出力してください。
テストケース $i$ について、$M_i$ 行出力し、$j$ 行目では ${K_i}_j$ に対する答えを出力し改行してください。
サンプル
サンプル1
入力
4 4 3 3 5 998244353 10 2 2 13 0 2 1 1000 450 1 10762384761907120098765617546523467851287698661854315
出力
85 367 165 111 843 1 1 397
例えばケース $1$ の $1$ 個目では $\sum_{i=0}^{3}{4^i} = 1+4+16+64 = 85$ であり $85 \mod 998 = 85$ なので答えは $85$ です。
また $2$ 個目では $\sum_{i=0}^{5}{4^i} = 1+4+16+64+256+1024 = 1365$ であり $1365 \mod 998 = 367$ なので答えは $367$ です。
ケース $4$ のように $64$ bit整数に収まらない入力が与えられる場合もあることに注意してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。