扩展欧拉定理

欧拉定理

欧拉定理：若 \(a\) 与 \(m\) 互质，则有 \[ a^{\varphi(m)}\equiv1(\mod m) \] 我们可以发现费马小定理其实就是欧拉定理的特殊情况。

证明的话，构造一个与 \(m\) 互质的数列操作，利用剩余系证明

扩展欧拉定理

扩展欧拉定理为 \[ a^b\equiv \begin{cases}a^{b\mod\varphi(p)},&\gcd(a,p)=1\\ a^b,&\gcd(a,p)\ne1,b<\varphi(p)\\ a^{b\mod\varphi(p)+\varphi(p)},&\gcd(a,p)\ne1,b\ge\varphi(p) \end {cases}\pmod p \] 证明请上面传送门

在程序上的体现就是加一个判断：如果 \(b\ge\varphi(p)\)，我们把 \(b\) 的模数加上一个 \(\varphi(p)\) 即可。

于是我们就能做掉P5091

输入幂数时取模即可。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cctype>
#define int long long
using namespace std;
inline int read(){
	int w=0,x=0;char c=getchar();
	while(!isdigit(c))w|=c=='-',c=getchar();
	while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return w?-x:x;
}
namespace star
{
	int n,m,b,phim;
	inline int fpow(int a,int b){
		int ans=1;
		for(;b;b>>=1,a=a*a%m)if(b&1)ans=ans*a%m;
		return ans;
	}
	inline void work(){
		n=read(),m=read();
		phim=m;
		int x=m;
		for(int i=2;i*i<=x;i++){
			if(!(x%i)){
				phim=phim-phim/i;
				while(!(x%i))x/=i;
			}
		}
		if(x!=1)phim=phim-phim/x;
		char c=getchar();
		bool ok=0;
		while(!isdigit(c))c=getchar();
		while(isdigit(c)){
			b=b*10+(c^48);c=getchar();
			if(b>=phim)ok=1,b%=phim;
		}
		if(!ok)printf("%lld\n",fpow(n,b));
		else printf("%lld\n",fpow(n,b+phim));
	}
}
signed main(){
	star::work();
	return 0;
}

CF906D

显然，对于对幂数取模的结果就是再次递归使用欧拉函数。递归求解即可。

先预处理出模数的多次取 phi 的结果然后递归。注意在快速幂的时候需要判断第二种情况。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cctype>
#define int long long
using namespace std;
inline int read(){
	int w=0,x=0;char c=getchar();
	while(!isdigit(c))w|=c=='-',c=getchar();
	while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return w?-x:x;
}
namespace star
{
	const int maxn=1e5+10;
	int mod,n,w[maxn],phi[maxn],tot;
	inline int fpow(int a,int b,int mod){
		int ans=1;
		bool ok=0;
		for(;b;b>>=1,a=a*a){
			if(a>=mod)ok=1,a%=mod;
			if(b&1)ans=ans*a;
			if(ans>=mod)ok=1;
			ans%=mod;
		}
		return ans+ok*mod;
	}
	int dfs(int l,int r,int dep){
		if(phi[dep]==1||w[l]==1) return 1;
		if(l==r)
			return w[l]>=phi[dep]?w[l]%phi[dep]+phi[dep]:w[l];
		return fpow(w[l],dfs(l+1,r,dep+1),phi[dep]);
	}
	inline void work(){
		n=read(),mod=phi[0]=read();
		for(int i=1;i<=n;i++)w[i]=read();
		while(phi[tot]!=1){
			int x=phi[tot++];phi[tot]=phi[tot-1];
			for(int i=2;i*i<=x;i++){
				if(!(x%i)){
					phi[tot]=phi[tot]-phi[tot]/i;
					while(!(x%i))x/=i;
				}
			}
			if(x>1)phi[tot]=phi[tot]-phi[tot]/x;
		}
		int q=read();
		while(q--){
			int l=read(),r=read();
			printf("%lld\n",dfs(l,r,0)%mod);
		}
	}
}
signed main(){
	star::work();
	return 0;
}

P3934

区间修改，单点查询，加上一个树状数组就行。每次的模数不一样，所以需要预处理一下欧拉函数。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cctype>
#define int long long
using namespace std;
inline int read(){
	int w=0,x=0;char c=getchar();
	while(!isdigit(c))w|=c=='-',c=getchar();
	while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return w?-x:x;
}
namespace star
{
	const int maxn=5e5+10,maxp=2e7+10;
	int mod,n,m,phi[maxp],tot,prime[maxp/10],cnt,a[maxn];
	inline int lowbit(int x){return x&(-x);}
	inline void update(int x,int y){
		for(;x<=n;x+=lowbit(x))a[x]+=y;
	}
	inline int query(int x){
		int ans=0;
		for(;x;x-=lowbit(x))ans+=a[x];
		return ans;
	}
	bool mark[maxp];
	inline void pre(int n){
		phi[1]=1;
		for(int i=2;i<=n;i++){
			if(!mark[i])prime[++cnt]=i,phi[i]=i-1;
			for(int j=1;j<=cnt and i*prime[j]<=n;j++){
				mark[i*prime[j]]=1;
				if(!(i%prime[j])){
					phi[i*prime[j]]=phi[i]*prime[j];
					break;
				}
				phi[i*prime[j]]=phi[i]*(prime[j]-1);
			}
		}
	}
	inline int fpow(int a,int b,int mod){
		int ans=1;
		bool ok=0;
		for(;b;b>>=1,a=a*a){
			if(a>=mod)ok=1,a%=mod;
			if(b&1)ans=ans*a;
			if(ans>=mod)ok=1;
			ans%=mod;
		}
		return ans+ok*mod;
	}
	int dfs(int l,int r,int mod){
		int w=query(l);
		if(mod==1||w==1) return 1;
		if(l==r)
			return w>=mod?w%mod+mod:w;
		return fpow(w,dfs(l+1,r,phi[mod]),mod);
	}
	inline void work(){
		n=read(),m=read();
		int pre=0,zp=0;
		for(int i=1;i<=n;i++)zp=read(),update(i,zp-pre),pre=zp;
		while(m--){
			if(read()==1){
				int l=read(),r=read(),k=read();
				update(l,k),update(r+1,-k);
			}else{
				int l=read(),r=read(),p=read();
				printf("%lld\n",dfs(l,r,p)%p);
			}
		}
	}
}
signed main(){
	star::pre(20000000);
	star::work();
	return 0;
}