题解：P4830 选择题

· · 题解

本题有两种解法，分别是

  1. 使用欧拉函数解决问题

    • 对于正整数 n，n 的欧拉函数 \varphi(n) 表示小于等于 n 且与 n 互质的正整数的个数。

    • 可利用以下两个性质解决本题：

      1. 如果 n 是质数，那么 \varphi(n)= n -1 ，因为只有 n 本身与它不互质。
      2. 如果 p,q 都是质数，那么 \varphi(pq)=\varphi(p)\varphi(q)=(p-1)(q-1)。
  2. 使用扩展 gcd 来求值
    • 这个太简单了，不想说了。

感谢查看！