[NICA #2] 亘久不变

Luogu
IDLGB3831
Time1000ms
Memory512MB
DifficultyP3
数论O2优化基环树
给定 $n$ 个正整数 $a_i$ 与三个正整数 $x,y,p$,定义一次对**非负整数** $t$ 的变换为: - 将 $t$ 替换为 $(xt+y)\bmod p$。 定义数 $t$ 是“$k$-不变”的,当且仅当其经过 $k$ 次变换后值不变。 小 Ran 希望知道给定的数组 $a$ 中有多少数是“$k$-不变”的,为了更加准确的知道答案,她会给出 $q$ 组 $k$ 进行询问。 ## Input 第一行四个正整数 $n,x,y,p$,意义同题目描述。 第二行 $n$ 个正整数,其中第 $i$ 个正整数为 $a_i$,意义同题目描述。 第三行一个正整数 $q$,意义同题目描述。 接下来 $q$ 行每行一个正整数 $k_i$,代表询问 $a$ 中有多少数是“$k_i$-不变”的。 ## Output 对每个询问输出一行一个正整数,表示答案。 [samples] ## Background 此世间,亘久不变之物若显真容,其必似华鸟风月般庄严凛然、隽美无二。 ## Note 数据保证,$1\le n\le 10^5$,$1\le p,q\le 10^3$,$1\le a_i,x,y,k_i\le 10^9$。 **注意 $p$ 不一定是质数。**
Samples
Input #1
5 2 3 7
2 3 4 5 6
5
1
2
3
4
5
Output #1
1
1
5
1
1
Input #2
5 3 8 4
2 3 4 5 1
5
1
2
3
4
5
Output #2
1
3
1
3
1
API Response (JSON)
{
  "problem": {
    "name": "[NICA #2] 亘久不变",
    "description": {
      "content": "给定 $n$ 个正整数 $a_i$ 与三个正整数 $x,y,p$,定义一次对**非负整数** $t$ 的变换为: - 将 $t$ 替换为 $(xt+y)\\bmod p$。 定义数 $t$ 是“$k$-不变”的,当且仅当其经过 $k$ 次变换后值不变。 小 Ran 希望知道给定的数组 $a$ 中有多少数是“$k$-不变”的,为了更加准确的知道答案,她会给出 $q$ 组 $k$ 进行询问。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB3831"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定 $n$ 个正整数 $a_i$ 与三个正整数 $x,y,p$,定义一次对**非负整数** $t$ 的变换为:\n\n- 将 $t$ 替换为 $(xt+y)\\bmod p$。\n\n定义数 $t$ 是“$k$-不变”的,当且仅当其经过 $k$ 次变换后值不变。\n\n小 Ran 希望知道给定的数组 $a$ 中有多少数是“$k$-不变”的,为了更加准确的知道答案,她会给出 $q$ 组 $k$ 进行询问。\n\n#...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments