信奥赛C++提高组csp-s之数论基础专题课：欧拉函数和欧拉定理2（编程案例实践）
信奥赛C++提高组csp-s之数论基础专题课：欧拉函数和欧拉定理2（编程案例实践）
信奥赛C++中的欧拉函数和欧拉定理是数论基础专题中重要内容。上次内容我们了讲解其数学原理，并举数学例子帮大家做了深入理解。本次课我们将讲解编程案例实践。
扩展欧拉定理
题目描述
给你三个正整数，a , m , b a,m,ba,m,b，你需要求：a b m o d m a^b \bmod mabmodm。
输入格式
一行三个整数，a , m , b a,m,ba,m,b。
输出格式
一个整数表示答案。
输入输出样例 1
输入 1
2 7 4输出 1
2输入输出样例 2
输入 2
998244353 12345 98765472103312450233333333333输出 2
5333说明/提示
注意输入格式，a , m , b a,m,ba,m,b依次代表的是底数、模数和次数。
【样例1 11解释】
2 4 m o d 7 = 2 2^4 \bmod 7 = 224mod7=2。
【数据范围】
对于100 % 100\%100%的数据，1 ≤ a ≤ 10 9 1\le a \le 10^91≤a≤109，1 ≤ b ≤ 10 20000000 ， 1 ≤ m ≤ 10 8 1\le b \le 10^{20000000}，1\le m \le 10^81≤b≤1020000000，1≤m≤108。
思路分析
本题要求计算a b m o d m a^b \bmod mabmodm，其中 b 可能是一个长度高达2 × 10 7 2\times 10^72×107的巨大整数，无法直接用整数存储。必须利用扩展欧拉定理来降低指数规模：
a b ≡ { a b ( m o d m ) b < φ ( m ) a b m o d φ ( m ) + φ ( m ) ( m o d m ) b ≥ φ ( m ) a^b \equiv \begin{cases} a^b \pmod{m} & b < \varphi(m) \\[1ex] a^{\,b \bmod \varphi(m) + \varphi(m)} \pmod{m} & b \ge \varphi(m) \end{cases}ab≡{ab(modm)abmodφ(m)+φ(m)(modm)b<φ(m)b≥φ(m)
其中φ ( m ) \varphi(m)φ(m)是欧拉函数（1 ≤ m ≤ 10 8 1\le m\le 10^81≤m≤108，可用试除法求出）。
算法步骤：
- 读入 (a, m) 和字符串 (b)。
- 特判 m = 1：直接输出 0。
- 计算φ ( m ) \varphi(m)φ(m)。
- 判断 b 与φ ( m ) \varphi(m)φ(m)的大小关系：
- 若 b 的十进制长度≤ 9 \le 9≤9，则可将 b 转为整数与φ ( m ) \varphi(m)φ(m)比较，若b < φ ( m ) b < \varphi(m)b<φ(m)，指数取 b 本身；否则指数取b m o d φ ( m ) + φ ( m ) b \bmod \varphi(m) + \varphi(m)bmodφ(m)+φ(m)。
- 若 b 的长度 (> 9)，则 b 一定不小于φ ( m ) \varphi(m)φ(m)，只需计算b m o d φ ( m ) b \bmod \varphi(m)bmodφ(m)，指数取该余数加φ ( m ) \varphi(m)φ(m)。
- 用快速幂计算a 指数 m o d m a^{\text{指数}} \bmod ma指数modm并输出。
代码实现
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;// 计算欧拉函数 phi(n) (n <= 1e8)intphi(intn){intres=n;for(inti=2;i*i<=n;++i){if(n%i==0){res=res/i*(i-1);while(n%i==0)n/=i;}}if(n>1)res=res/n*(n-1);returnres;}// 快速幂：计算 a^b % modllqpow(ll a,ll b,ll mod){ll r=1%mod;while(b){if(b&1)r=(r*a)%mod;a=(a*a)%mod;b>>=1;}returnr;}intmain(){inta,m;string b;cin>>a>>m>>b;if(m==1){// 模数为1，任何数模1都是0cout<<0<<endl;return0;}intp=phi(m);// p = φ(m)ll e;// 最终指数intlen=b.size();if(len<=9){// b 可以用整数表示，直接比较ll B=stoll(b);if(B<p)e=B;else{// 虽然 B >= p，但为了保险仍取余数并加上 pe=B%p+p;}}else{// b 长度 >9，肯定 >= p，只需计算余数ll r=0;for(charc:b){r=(r*10+(c-'0'))%p;}e=r+p;}ll ans=qpow(a%m,e,m);cout<<ans<<endl;return0;}功能分析
- 欧拉函数计算：使用试除法，时间复杂度O ( m ) O(\sqrt{m})O(m)，对于m ≤ 10 8 m\le 10^8m≤108完全可行。
- 大整数处理：通过字符串读入 b，利用长度比较和逐位取模避免溢出，同时正确判断 b 与φ ( m ) \varphi(m)φ(m)的大小关系，满足扩展欧拉定理的使用条件。
- 指数确定：根据比较结果，选择直接使用 b 或b m o d φ ( m ) + φ ( m ) b \bmod \varphi(m) + \varphi(m)bmodφ(m)+φ(m)作为最终指数，保证定理适用。
- 快速幂：使用二进制拆分，时间复杂度O ( log 指数 ) O(\log \text{指数})O(log指数)，指数不超过2 φ ( m ) ≤ 2 × 10 8 2\varphi(m) \le 2\times 10^82φ(m)≤2×108，运行极快。
- 边界处理：特判 m=1，避免后续运算；取模前先将 a 对 m 取余，防止中间溢出。
更多系列知识，请查看专栏：《信奥赛C++提高组csp-s知识详解及案例实践》：
https://blog.csdn.net/weixin_66461496/category_13113932.html
各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}1、csp信奥赛高频考点知识详解及案例实践：
CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转
CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转
信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html
2、csp信奥赛冲刺一等奖有效刷题题解：
CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）
https://blog.csdn.net/weixin_66461496/category_13125089.html
3、GESP C++考级真题题解：
GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转
GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转
GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html
4、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：
https://edu.csdn.net/lecturer/7901 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}