扩展欧拉定理以及练习题

扩展欧拉定理

定理

定理内容

$$a^b\equiv \{\begin{array}{ll}{a}^{b\mathrm{mod}\phi (m)}& \text{如果 }\gcd (a,m)=1,\\ a^b& \text{如果 }\gcd (a,m)\ne 1\text{ 且 }b<\phi (m),\\ a^{b\mathrm{mod}\phi (m)+\phi (m)}& \text{如果 }\gcd (a,m)\ne 1\text{ 且 }b\ge \phi (m).\end{array}(\mathrm{mod}m)$$

其中 $\phi$ 为欧拉函数。

例子：
计算 $7^{1000}\mathrm{mod}10$：

1. $\phi (10)=4$（因为与 10 互质的数为 1, 3, 7, 9）。
2. $\gcd (7,10)=1$，所以直接应用欧拉定理：
   $$7^{1000}=7^{4\times 250}=7^0\equiv 1(\mathrm{mod}10).$$

证明

这里偷懒，贴了deepseek的证明：

习题

模板题luogu5091

link

不过注意到 $b$ 的值域达到了 $10^{2\times 10^7}$，所以需要读入的时候就可以进行取模了，这样子这题就做完了。

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
#define fr(i,a,b,k) for(int i=a;i!=b;i+=k)// a<b a>b
using namespace std;
const int N=1e6+1;
int t,n,m,mod,a,b;
inline int qmi(int x,int y)
{
	int res=1;
	while(y>0)
	{
		if(y&1)
			res*=x,res%=mod;
		x*=x,x%=mod,y>>=1;
	}
	return res;
}
inline int read()
{
	int x=0;
	bool f=0;
	char c=getchar();
	while(c>'9'||c<'0')
		c=getchar();
	while(c<='9'&&c>='0')
		x=x*10+c-'0',c=getchar(),f|=(x>=m),x%=m;
	return x+f*m;
}
int phi(int x)
{
	int ans=x,y=sqrt(x);
	fr(i,2,y+1,1)
	{
		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;
}
signed main()
{
	//IOS;
	cin>>a>>mod;
	m=phi(mod);
	b=read();
	cout<<qmi(a,b);
	return 0;
}

代码是很久以前写的，码风烂，勿喷。

还有一些注意的点：

求单个欧拉函数的时间复杂度是 $\sqrt{n}$，但是如果求多个的话，可以线性筛 $O(V)$ 解决。

其次你可能会疑惑，这代码里也没有判断 $\gcd (a,m)$ 是否为 $1$ 啊。

其实是简化了的，根据欧拉定理：
当 $a,m\in \mathbb{Z}$ ，且 $\gcd (a,m)=1$ 时有： $a^{\phi (m)}\equiv 1(\mathrm{mod}m)$ 。

此时 $a^{b\mathrm{mod}\phi (m)+\phi (m)}=a^{b\mathrm{mod}\phi (m)}$

所以写代码时一般认为扩展欧拉定理长这样：

当 $a,m\in \mathbb{Z}$ 时有：
$$a^b\equiv \{\begin{array}{cl}{a}^b& ,b<\phi (m)\\ a^{b\mathrm{mod}\phi (m)+\phi (m)}& ,b\ge \phi (m)\end{array}(\mathrm{mod}m)$$

练习题

这里放几道题，由于作者现在还没有做出来这些题，所以先放着，以后会出相应的题解。

• 洛谷P4139 lnik
• CF906D 洛谷 CF
• CF615D 洛谷 CF
• CF17D 洛谷 CF