{"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## Input\n\n第一行四个正整数 $n,x,y,p$，意义同题目描述。\n\n第二行 $n$ 个正整数，其中第 $i$ 个正整数为 $a_i$，意义同题目描述。\n\n第三行一个正整数 $q$，意义同题目描述。\n\n接下来 $q$ 行每行一个正整数 $k_i$，代表询问 $a$ 中有多少数是“$k_i$-不变”的。\n\n## Output\n\n对每个询问输出一行一个正整数，表示答案。\n\n[samples]\n\n## Background\n\n此世间，亘久不变之物若显真容，其必似华鸟风月般庄严凛然、隽美无二。\n\n## Note\n\n数据保证，$1\\le n\\le 10^5$，$1\\le p,q\\le 10^3$，$1\\le a_i,x,y,k_i\\le 10^9$。\n\n**注意 $p$ 不一定是质数。**","is_translate":false,"language":"English"}],"meta":{"iden":"LGB3831","tags":["数论","O2优化","基环树"],"sample_group":[["5 2 3 7\n2 3 4 5 6\n5\n1\n2\n3\n4\n5","1\n1\n5\n1\n1\n"],["5 3 8 4\n2 3 4 5 1\n5\n1\n2\n3\n4\n5","1\n3\n1\n3\n1"]],"created_at":"2026-03-03 11:09:25"}}