「Cfz Round 3」Change

Luogu

IDLGP10030

Time1000ms

Memory512MB

DifficultyP2

数学洛谷原创Special JudgeO2优化洛谷月赛

给定一个质数 $p$ 和三个整数 $a,b,c$，你需要对一个初始为 $0$ 的整数 $x$ 进行操作，每次操作可以进行如下的两种之一： - 第一种操作：令 $x$ 的值变为 $(x \times a) \bmod p$。 - 第二种操作：令 $x$ 的值变为 $(x+b) \bmod p$。其中，$\bmod$ 表示**取模**运算。你需要求出能否在**正整数次**操作后得到 $c$，若能则输出 `Yes`，否则输出 `No`。本题中字符串大小写不敏感，即 `yes`、`yeS`、`yEs`、`Yes`、`YEs`、`YeS`、`yES`、`Yes` 都被认为是 `Yes`，`No` 同理。 ## Input **本题有多组测试数据。** 第一行输入一个整数 $T$，表示测试数据组数。接下来依次输入每组测试数据。对于每组测试数据，输入一行四个整数 $p,a,b,c$。 ## Output 对于每组测试数据，输出一行： - 若能在正整数次操作后得到 $c$，则输出 `Yes`； - 若不能在正整数次操作后得到 $c$，则输出 `No`。本题中字符串大小写不敏感，即 `yes`、`yeS`、`yEs`、`Yes`、`YEs`、`YeS`、`yES`、`Yes` 都被认为是 `Yes`，`No` 同理。 [samples] ## Note #### 「样例解释 #1」对于第 $1$ 组数据，进行 $1$ 次第二种操作后进行 $2$ 次第一种操作即可。对于第 $2$ 组数据，进行 $1$ 次第二种操作后进行 $1$ 次第一种操作即可。对于第 $3$ 组数据，可以证明无论如何操作都无法得到 $3$。 #### 「数据范围」对于所有数据，$1\le T \le 100$，$0\le a,b,c < p \le 10^9$，保证 $p$ 是质数。 **只有你通过本题的所有测试点，你才能获得本题的分数。**

Samples

Input #1

Output #1

Yes
Yes
No

API Response (JSON)

{
  "problem": {
    "name": "「Cfz Round 3」Change",
    "description": {
      "content": "给定一个质数 $p$ 和三个整数 $a,b,c$，你需要对一个初始为 $0$ 的整数 $x$ 进行操作，每次操作可以进行如下的两种之一： - 第一种操作：令 $x$ 的值变为 $(x \\times a) \\bmod p$。 - 第二种操作：令 $x$ 的值变为 $(x+b) \\bmod p$。 其中，$\\bmod$ 表示**取模**运算。 你需要求出能否在**正整数次**操作后得到 $c$，",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10030"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一个质数 $p$ 和三个整数 $a,b,c$，你需要对一个初始为 $0$ 的整数 $x$ 进行操作，每次操作可以进行如下的两种之一：\n\n- 第一种操作：令 $x$ 的值变为 $(x \\times a) \\bmod p$。\n- 第二种操作：令 $x$ 的值变为 $(x+b) \\bmod p$。\n\n其中，$\\bmod$ 表示**取模**运算。\n\n你需要求出能否在**正整数次**操作后得到 $c$，...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments