题意

题目描述

给你三个正整数，$a,m,b$,你需要求：

$a^b \mod m$

输入输出格式

输入格式：

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

输出格式：

一个整数表示答案

输入输出样例

输入样例#1：
复制

2 7 4

输出样例#1：
复制

输入样例#2：
复制

998244353 12345 98765472103312450233333333333

输出样例#2：
复制

说明

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

样例1解释：

$2^4 \mod 7 = 2$

输出2

数据范围：

对于全部数据：

$1≤a≤10^9$

$1≤b≤10^{20000000}$

$1≤m≤10^6$

分析

费马小定理

当 $a,p\in \mathbb{Z}$ 且 $p$ 为质数，且 $a\not\equiv 0\pmod{p}$ 时有：

$a^{p-1}\equiv 1\pmod{p}$ 。

所以 $a^b\equiv a^{b\bmod (p-1)}\pmod p$ 。

欧拉定理

当 $a,m\in \mathbb{Z}$ ，且 $\gcd(a,m)=1$ 时有：

$a^{\varphi(m)}\equiv 1\pmod{m}$ 。

这里 $\varphi(x)$ 是数论中的欧拉函数。

所以 $a^b\equiv a^{b\bmod \varphi(m)}\pmod m$ 。

扩展欧拉定理

当 $a,m\in \mathbb{Z}$ 时有：

$a^b\equiv\left\{\begin{matrix}a^b&,b<\varphi(m)\\a^{b\bmod\varphi(m)+\varphi(m)}&,b\ge\varphi(m)\end{matrix}\right.\pmod m$ 。

对于那个高精度整数，一边乘10相加，一遍取模即可。时间复杂度$O(\sqrt m+\lg b+\log_2 m)$

代码

#include<bits/stdc++.h>

#define rg register

#define il inline

#define co const

template<class T>il T read(){

    rg T data=0,w=1;rg char ch=getchar();

    while(!isdigit(ch)) {if(ch=='-') w=-1;ch=getchar();}

    while(isdigit(ch)) data=data*10+ch-'0',ch=getchar();

    return data*w;

}

template<class T>il T read(rg T&x) {return x=read<T>();}

typedef long long ll;

int main(){

	int a=read<int>(),m=read<int>();

	int phi=m,mm=m;

	for(int i=2;i*i<=mm;++i)if(mm%i==0){

		phi=phi/i*(i-1);

		while(mm%i==0) mm/=i;

	}

	if(mm>1) phi=phi/mm*(mm-1);

	int b=0,flag=0;

	char ch=getchar();

	while(!isdigit(ch)) ch=getchar();

	while(isdigit(ch)){

		b=b*10+ch-'0',ch=getchar();

		if(b>=phi) b%=phi,flag=1;

	}

	if(b>=phi) b%=phi,flag=1;

	if(flag) b+=phi;

	int ans=1;

	for(;b;b>>=1,a=(ll)a*a%m)

		if(b&1) ans=(ll)ans*a%m;

	printf("%d\n",ans);

	return 0;

}

巴特西

LG5901 【模板】欧拉定理

题意