Sum of Pow of Mod of Linear

AtCoder

IDabc429_g

Time4000ms

Memory256MB

Difficulty—

You are given integers $N,M,A,B,X,R$. Find the remainder when $\displaystyle \sum_{k=0}^{N-1} X^{(Ak+B) \bmod M}$ is divided by $R$. You are given $T$ test cases, so find the answer for each of them. ## Constraints * $1\le T\le 100$ * $1\le N,M,R\le 10^9$ * $0\le A,B < M$ * $1\le X < R$ * All input values are integers. ## Input The input is given from Standard Input in the following format: $T$ $\text{case}_1$ $\text{case}_2$ $\vdots$ $\text{case}_T$ Each test case $\text{case}_i$ is given in the following format: $N$ $M$ $A$ $B$ $X$ $R$ [samples]

Samples

Input #1

3
4 5 2 1 2 1000000000
777 429 33 58 1 1000000000
20251025 429429 777 1025 575757 998244353

Output #1

15
777
445271630

Consider the first test case.

*   When $k=0$: $\displaystyle X^{(Ak+B) \bmod M}=2^{(2\times 0+1) \bmod 5}=2^1=2$.
*   When $k=1$: $\displaystyle X^{(Ak+B) \bmod M}=2^{(2\times 1+1) \bmod 5}=2^3=8$.
*   When $k=2$: $\displaystyle X^{(Ak+B) \bmod M}=2^{(2\times 2+1) \bmod 5}=2^0=1$.
*   When $k=3$: $\displaystyle X^{(Ak+B) \bmod M}=2^{(2\times 3+1) \bmod 5}=2^2=4$.

From the above, the desired value is the remainder when $2+8+1+4$ is divided by $1000000000$, which is $15$. Therefore, print $15$ on the $1$st line.

API Response (JSON)

{
  "problem": {
    "name": "Sum of Pow of Mod of Linear",
    "description": {
      "content": "You are given integers $N,M,A,B,X,R$. Find the remainder when $\\displaystyle \\sum_{k=0}^{N-1} X^{(Ak+B) \\bmod M}$ is divided by $R$. You are given $T$ test cases, so find the answer for each of them.",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc429_g"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given integers $N,M,A,B,X,R$.\nFind the remainder when $\\displaystyle \\sum_{k=0}^{N-1} X^{(Ak+B) \\bmod M}$ is divided by $R$.\nYou are given $T$ test cases, so find the answer for each of them.\n...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments