No.3310 mod998
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もしくは右上の雲マークをクリックしてアカウントを作成してください。