专栏文章

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

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

文章操作

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

当前评论
1 条
当前快照
1 份
快照标识符
@mipkekxg
此快照首次捕获于
2025/12/03 13:26
3 个月前
此快照最后确认于
2025/12/03 13:26
3 个月前
查看原文
这道题目让我们求11到202320232023^{2023}中有几个与20232023互质的数，一看就是用欧拉函数。

前置知识 ：欧拉函数

具体的推导这里就不说了，欧拉函数的公式：
φ(n)=n⋅(1−1p1)⋅(1−1p2)⋅…⋅(1−1pm)\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)
（ p1,p2,...pmp_1, p_2, ... p_m为m的不同质因数）
那么知道了这个公式，我们就可以做题了。
2023=7∗1722023 = 7 * 17^2 ，所以 只需要让 20232023⋅67⋅16172023 ^ {2023} \cdot \frac{6}{7} \cdot \frac{16}{17} 就ok了。
（20232023⋅67⋅1617=1632⋅202320222023^{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;
}
最后答案应该是 640720414 \large640720414。
完结撒花！

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...