专栏文章

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

P12216题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipk1kb0
此快照首次捕获于
2025/12/03 13:16
3 个月前
此快照最后确认于
2025/12/03 13:16
3 个月前
查看原文

前言

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

分析

首先,我们都知道,与 20232023 互质的数一定与 202320232023^{2023} 互质。那么我们就可以将题目转化为求 [1,20232023][1,2023^{2023}] 范围内与 202320232023^{2023} 互质的数。
因为欧拉函数的性质,所以我们要先对 20232023 进行质因数分解,2023=7×1722023 = 7 \times 17^2,故 φ(20232023)=20232023×67×1617\varphi (2023^{2023}) = 2023^{2023} \times \frac{6}{7} \times \frac{16}{17},经过简单计算后得到 φ(20232023)=1632×20232023\varphi (2023^{2023}) = 1632 \times 2023^{2023},由于题目要求我们算出这个数对 109+710^9+7 取模之后的结果,所以我们就想到快速幂计算出答案。
所以最后只要输出 1632×20232023mod(109+7)1632 \times 2023^{2023} \bmod (10^9+7) 即可。我们可以用快速幂来求出这个答案,当然数据这么小直接循环暴力也是可行的,实在不行你可以在电脑里的计算器上算出然后输出,最终答案为 640720414640720414

评论

0 条评论,欢迎与作者交流。

正在加载评论...