問題一覧 > 通常問題

No.3310 mod998

レベル : / AI推定難易度 : 1250 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 40
作問者 : 👑 ArcAki / テスター : chiaoi
お気に入りにしたユーザー ProblemId : 12166 / 自分の提出
問題文最終更新日: 2025-10-24 17:18:26
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
yukicoder contest 486 オムニバス (順位表) の他の問題:

Story

Ah, yes, the usual $\mod998$ ...wait, what?!

Problem Statement

You are given $T$ test cases. Solve the following problem for each test case.
You are given a non-negative integer $N$ and a positive integer $M$. You are also given $M$ non-negative integers $K_1,\ K_2,\ \cdots\ K_M$. For each $K_j$,
find $(\sum_{i=0}^{K_j}{{N}^i)} \mod 998$.
In this problem, $0^0 = 1$.

Input

The input is given in the following format.
$T$
$testcase_1$
$\vdots$
$testcase_T$

Here, $testcase_i$ represents the $i$-th test case, and each is given in the following format.

$N_i\ M_i$
${K_i}_1$
$\vdots$
${K_i}_{M_i}$

  • All input values are integers.
  • $1 ≤ T ≤ 50$
  • Each test case satisfies the following:
    • $0 ≤ N_i < 998$
    • $1 ≤ M_i ≤ 10^3$
    • $0 ≤ {K_i}_j < 10^{10^{5}}$
    • The total number of digits of the ${K_i}_j$ in a test case, written in base $10$, is at most $10^5$.

Output

Output the answers for the test cases in order.
For test case $i$, output $M_i$ lines. On line $j$, output the answer for ${K_i}_j$, followed by a newline.

Sample

Sample 1
Input
4
4 3
3
5
998244353
10 2
2
13
0 2
1
1000
450 1
10762384761907120098765617546523467851287698661854315
Output
85
367
165
111
843
1
1
397

For example, for query $1$ of case $1$, $\sum_{i=0}^{3}{4^i} = 1+4+16+64 = 85$ and $85 \mod 998 = 85$, so the answer is $85$.
For query $2$, $\sum_{i=0}^{5}{4^i} = 1+4+16+64+256+1024 = 1365$ and $1365 \mod 998 = 367$, so the answer is $367$.
Note that, as in case $4$, the input may contain values that do not fit in a $64$ bit integer.

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