扩展欧拉定理

前置知识

欧拉定理

定义

对于任意正整数 a,b,c，必定满足下式:

$$a^b\ mod\ c= \left \{ \begin{matrix} {a^b\ mod\ c} &b<ψ(c)\\ {a^{b\ mod\ ψ(c)+ψ(c)}}\ mod\ c &b\geq ψ(c) \end{matrix} \right.$$

证明

略过，后补

代码实现

typedef long long ll;
typedef unsigned long long ull;
typedef long double lb;
ll euler(ll n)//欧拉函数
{
	ll ans=n;
	for(long long i=2; i*i<=n; ++i)
		if(n%i==0)
		{
			ans=ans-ans/i;
			while(n%i==0)  n/=i;
		}
	if(n>1)  ans=ans-ans/n;
	return ans;
}
inline ll ksc(ull x,ull y,ll p) //O(1)快速乘（防爆long long）
{
	return (x*y-(ull)((lb)x/p*y)*p+p)%p;
}
inline ll fastPow(ll a,ll k,ll p)// a 底数， k 指数， 求 a^k mod p
{
	long long res = 1;
	a%=p;
	while(k > 0)
	{
		if (k & 1) res =ksc(res,a,p);
		a = ksc(a,a,p);
		k >>= 1;
	}
	return res;
}
inline ll Exeuler_prince(ll a,string s,ll c)//a是底数，s是次数b的字符串形式，c为模数
{
	ll wc=euler(c),flag=0,b=0;//ψ(c) ,flag,b是否比ψ(c)大 
	for(int i=0; i<s.size(); ++i)
	{
		b=b*10+s[i]-'0';
		if(b>=wc) flag=1;
		b%=wc;
	}
	if(flag) b+=wc;
	return fastPow(a,b,c);
}

应用

配合大数取余求解

例题

P5091 【模板】扩展欧拉定理

参考博文

扩展欧拉定理 —— 欧拉定理的一般情况