专栏文章
题解:P12216 [蓝桥杯 2023 国 Java B] 互质
P12216题解参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性,并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mipk1kb0
- 此快照首次捕获于
- 2025/12/03 13:16 3 个月前
- 此快照最后确认于
- 2025/12/03 13:16 3 个月前
前言
由于本题是结论题,知道如何推导即可,我希望别人能够学会推导过程而不是一味地抄代码,所以不放代码,这里是我的 AC 记录。
分析
首先,我们都知道,与 互质的数一定与 互质。那么我们就可以将题目转化为求 范围内与 互质的数。
因为欧拉函数的性质,所以我们要先对 进行质因数分解,,故 ,经过简单计算后得到 ,由于题目要求我们算出这个数对 取模之后的结果,所以我们就想到快速幂计算出答案。
所以最后只要输出 即可。我们可以用快速幂来求出这个答案,当然数据这么小直接循环暴力也是可行的,实在不行你可以在电脑里的计算器上算出然后输出,最终答案为 。
相关推荐
评论
共 0 条评论,欢迎与作者交流。
正在加载评论...