『算法-ACM竞赛-数学-数论』欧拉降幂-P5091 欧拉定理

『算法-ACM 竞赛-数学-数论』欧拉降幂-P5091 欧拉定理

题目背景

出题人也想写有趣的题面，可惜并没有能力。

题目描述

给你三个正整数，a,m,ba,m,b，你需要求：ab mod ma^b \bmod m

输入格式

一行三个整数，a,m,ba,m,b

输出格式

一个整数表示答案

输入输出样例

输入 #1 
2 7 4
输出 #1 
2
输入 #2 
998244353 12345 98765472103312450233333333333
输出 #2 
5333

说明/提示

注意输入格式，a,m,ba,m,b 依次代表的是底数、模数和次数

【样例 11 解释】
24 mod 7=22^4 \bmod 7 = 2

【数据范围】
对于 100%100\% 的数据，1≤a≤1091\le a \le 10^9，1≤b≤1020000000，1≤m≤1081\le b \le 10^{20000000}，1\le m \le 10^8。

这个题是模板欧拉降幂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#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;
}