当前位置：首页 > news >正文

洛谷 P5091：【模板】扩展欧拉定理

news 2025/5/29 8:27:31

【题目来源】
https://www.luogu.com.cn/problem/P5091

【题目描述】
给你三个正整数，底数 a，模数 m，次数 b，你需要求：a^b mod m。

【输入格式】
一行三个整数，底数 a，模数 m，次数 b。

【输出格式】
一个整数表示答案。

【输入样例】
998244353 12345 98765472103312450233333333333

【输出样例】
5333

【数据范围】
对于 100% 的数据，1≤a≤10^9，1≤b≤10^20000000，1≤m≤10^8。

【算法分析】
● 通过字符串解析大指数，并应用欧拉定理降幂，解决大指数的溢出问题。

● 扩展欧拉定理：对于任意整数 a 和模数 n，若 x≥φ(n)，则有： $a^x=a^{x \mod \phi (n)+\phi (n)} (mod \ n)$ 。
这种扩展使得我们能够在 x 非常大的情况下，通过对 x 取模 φ(n) 来简化计算。

● 快读：https://blog.csdn.net/hnjzsyjyj/article/details/120131534

int read() { //fast readint x=0,f=1;char c=getchar();while(c<'0' || c>'9') { //!isdigit(c)if(c=='-') f=-1;c=getchar();}while(c>='0' && c<='9') { //isdigit(c)x=x*10+c-'0';c=getchar();}return x*f;
}

● 快速幂：https://blog.csdn.net/hnjzsyjyj/article/details/143168167

int fastPow(LL a,LL b,LL p) {LL ans=1;while(b) {if(b & 1) ans=ans*a%p;a=a*a%p;b>>=1;}return ans%p;
}

● 欧拉函数：https://blog.csdn.net/hnjzsyjyj/article/details/148159326

int oula_phi(int x) {int ans=x;for(int i=2; i*i<=x; i++) {if(x%i==0) {ans=ans/i*(i-1);while(x%i==0) x/=i;}}if(x>1) ans=ans/x*(x-1);return ans;
}

【算法代码】

#include <bits/stdc++.h>
#define int long long
using namespace std;int gcd(int a, int b) {if(b==0) return a;else return gcd(b,a%b);
}int oula_phi(int x) {int ans=x;for(int i=2; i*i<=x; i++) {if(x%i==0) {ans=ans/i*(i-1);while(x%i==0) x/=i;}}if(x>1) ans=ans/x*(x-1);return ans;
}int fastPow(int a,int b,int p) {int ans=1;while(b) {if(b & 1) ans=ans*a%p;a=a*a%p;b>>=1;}return ans%p;
}int parseBigInt(string s,int t) {int ans=0;bool flag=false;for(char c:s) {ans=ans*10+(c-'0');if(ans>=t) {flag=true;ans%=t;}}return flag?ans+t:ans;
}signed main() {int a,m;string b_str;cin>>a>>m>>b_str;if(m==1) {cout<<0<<endl;return 0;}int t=oula_phi(m);int b_mod=parseBigInt(b_str,t);if(gcd(a,m)==1) b_mod%=t;cout<<fastPow(a,b_mod,m)<<endl;return 0;
}/*
in:
998244353 12345 98765472103312450233333333333out:
5333
*/

【参考文献】
https://www.luogu.com.cn/problem/solution/P5091
https://blog.csdn.net/hnjzsyjyj/article/details/143168167
https://blog.csdn.net/hnjzsyjyj/article/details/148159326
https://blog.csdn.net/hnjzsyjyj/article/details/148179867

查看全文

http://www.xdnf.cn/news/674785.html