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

· · 题解

这道题目让我们求12023^{2023}中有几个与2023互质的数,一看就是用欧拉函数。

前置知识 :欧拉函数

具体的推导这里就不说了,欧拉函数的公式:

\varphi(n) = n \cdot \left(1 - \frac{1}{p_1}\right) \cdot \left(1 - \frac{1}{p_2}\right) \cdot \ldots \cdot \left(1 - \frac{1}{p_m}\right)

p_1, p_2, ... p_m为m的不同质因数)

那么知道了这个公式,我们就可以做题了。

($2023^{2023}\cdot \frac{6}{7} \cdot \frac{16}{17} = 1632 \cdot 2023^{2022}$) ## 代码如下: ```cpp #include <bits/stdc++.h> using namespace std; const int M = 1e9+7; int main() { long long ans = 1632; for(int i = 1; i <= 2022; i++) { ans *= 2023; ans %= M; } cout << ans; return 0; } ``` 最后答案应该是 $ \large640720414$。 完结撒花!