数学--数论--欧拉降幂--P5091 欧拉定理
数学--数论--欧拉降幂--P5091 欧拉定理
风骨散人Chiam
发布于 2020-10-28 10:23:48
发布于 2020-10-28 10:23:48
题目背景
出题人也想写有趣的题面，可惜并没有能力。
题目描述
给你三个正整数，a,m,ba,m,ba,m,b，你需要求：ab mod ma^b \bmod mabmodm
输入格式
一行三个整数，a,m,ba,m,ba,m,b
输出格式
一个整数表示答案
输入输出样例
输入 #1 复制
2 7 4输出 #1 复制
2输入 #2 复制
998244353 12345 98765472103312450233333333333输出 #2 复制
5333说明/提示
注意输入格式，a,m,ba,m,ba,m,b 依次代表的是底数、模数和次数
【样例 111 解释】 24 mod 7=22^4 \bmod 7 = 224mod7=2
【数据范围】 对于 100%100\%100% 的数据，1≤a≤1091\le a \le 10^91≤a≤109，1≤b≤1020000000，1≤m≤1081\le b \le 10^{20000000}，1\le m \le 10^81≤b≤1020000000，1≤m≤108。
这个题是模板欧拉降幂
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll a,m,b;
inline ll read(ll m){
register ll x=0,f=0;char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)){
x=x*10+ch-'0';
if(x>=m) f=1;
x%=m;ch=getchar();
}
return x+(f==1?m:0);
}
ll phi(ll n){
ll ans=n,m=sqrt(n);
for(ll i=2;i<=m;i++){
if(n%i==0){
ans=ans/i*(i-1);
while(n%i==0) n/=i;
}
}
if(n>1) ans=ans/n*(n-1);
return ans;
}
ll fast_pow(ll a,ll b,ll p){
ll ret=1;
for(;b;b>>=1,a=a*a%p)
if(b&1) ret=ret*a%p;
return ret;
}
int main()
{
scanf("%lld%lld",&a,&m);
b=read(phi(m));
printf("%lld\n",fast_pow(a,b,m));
return 0;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-03-01 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录