题解：P12216 [蓝桥杯 2023 国 Java B] 互质

· · 题解

前言

由于本题是结论题，知道如何推导即可，我希望别人能够学会推导过程而不是一味地抄代码，所以不放代码，这里是我的 AC 记录。

分析

首先，我们都知道，与 2023 互质的数一定与 2023^{2023} 互质。那么我们就可以将题目转化为求 [1,2023^{2023}] 范围内与 2023^{2023} 互质的数。

因为欧拉函数的性质，所以我们要先对 2023 进行质因数分解，2023 = 7 \times 17^2，故 \varphi (2023^{2023}) = 2023^{2023} \times \frac{6}{7} \times \frac{16}{17}，经过简单计算后得到 \varphi (2023^{2023}) = 1632 \times 2023^{2023}，由于题目要求我们算出这个数对 10^9+7 取模之后的结果，所以我们就想到快速幂计算出答案。

所以最后只要输出 1632 \times 2023^{2023} \bmod (10^9+7) 即可。我们可以用快速幂来求出这个答案，当然数据这么小直接循环暴力也是可行的，实在不行你可以在电脑里的计算器上算出然后输出，最终答案为 640720414。