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

· · 题解

找了半天终于找到一道能交题解的水题了。

言归正传，我们直接看思路。

前置知识：

欧拉函数。

思路：

要解决这道题，我们需要使用到欧拉函数计算在区间 \begin{bmatrix} 1, 2023^{2023} \end{bmatrix} 内与 2023 互质的整数的个数。但是直接计算这个范围内的数肯定会超时，所以我们就需要利用数论中的欧拉函数和容斥原理了，那么废话不多说，我们直接进入正题。

正题：

Step1 分解质因数：

首先，我们需要先将 2023 的质因数分解，也就是：

\begin{aligned} \ 2023 &= 7 \times 17 \times 17 \\ &= 7 \times 17^2 \end{aligned}

Step2 求整数个数：

将 2023 的质因数分解后，我们可以利用欧拉函数来求与 2023 互质的数的个数，也就是：

\begin{aligned} \ φ(2023)&=2023 \times (1 - \frac{1}{7}) \times (1 - \frac{1}{17})\\ &= 2023 \times (\frac{6}{7}) \times (\frac{16}{17}) \\ &= 1632 \end{aligned}

所以与 2023 互质的数就会有 1632 个。

Step3 求区间互质：

于是在这个区间的 \begin{bmatrix} 1 , 2023^{2023} \end{bmatrix} 中，与 2023 互质的个数为：

(2023^{2023}) \times \frac{φ(2023)}{2023} =2023^{(2023 - 1)} \times φ(2023) = 2023^{2022} \times 1632

Step4 求最终答案：

最后用快速幂求出 2023^{2022} \times 1632 \bmod (10^9+7) 就是最终答案了。

AC CODE：

#include <bits/stdc++.h>
using namespace std;
const int MOD=1e9+7;
long long ksm(long long a,long long b,long long mod){
    long long ans=1;
    a%=mod;
    while(b>0){
        if(b%2==1) ans=(ans*a)%mod;
        a=(a*a)%mod;
        b/=2;
    }
    return ans;
}
int main(){
    long long p1=2023*(7-1)/7*(17-1)/17;
    long long p2=ksm(2023,2022,MOD);
    cout<<(p1*p2)%MOD;
    return 0;
}