信奥赛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输入 12 7 4输出 12输入输出样例 2输入 2998244353 12345 98765472103312450233333333333输出 25333说明/提示注意输入格式a , m , b a,m,ba,m,b依次代表的是底数、模数和次数。【样例1 11解释】2 4 m o d 7 2 2^4 \bmod 7 224mod72。【数据范围】对于100 % 100\%100%的数据1 ≤ a ≤ 10 9 1\le a \le 10^91≤a≤1091 ≤ b ≤ 10 20000000 1 ≤ m ≤ 10 8 1\le b \le 10^{20000000}1\le m \le 10^81≤b≤10200000001≤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并输出。代码实现#includebits/stdc.husingnamespacestd;typedeflonglongll;// 计算欧拉函数 phi(n) (n 1e8)intphi(intn){intresn;for(inti2;i*in;i){if(n%i0){resres/i*(i-1);while(n%i0)n/i;}}if(n1)resres/n*(n-1);returnres;}// 快速幂计算 a^b % modllqpow(ll a,ll b,ll mod){ll r1%mod;while(b){if(b1)r(r*a)%mod;a(a*a)%mod;b1;}returnr;}intmain(){inta,m;string b;cinamb;if(m1){// 模数为1任何数模1都是0cout0endl;return0;}intpphi(m);// p φ(m)ll e;// 最终指数intlenb.size();if(len9){// b 可以用整数表示直接比较ll Bstoll(b);if(Bp)eB;else{// 虽然 B p但为了保险仍取余数并加上 peB%pp;}}else{// b 长度 9肯定 p只需计算余数ll r0;for(charc:b){r(r*10(c-0))%p;}erp;}ll ansqpow(a%m,e,m);coutansendl;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运行极快。边界处理特判 m1避免后续运算取模前先将 a 对 m 取余防止中间溢出。更多系列知识请查看专栏《信奥赛C提高组csp-s知识详解及案例实践》https://blog.csdn.net/weixin_66461496/category_13113932.html各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}1、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html2、csp信奥赛冲刺一等奖有效刷题题解CSP信奥赛C初赛及复赛高频考点真题解析持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html3、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.html4、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}