欧拉函数|欧拉定理

摘要

复习一下欧拉定理,顺便打了洛谷新出炉的模板~

欧拉函数

定义

欧拉函数用希腊字母 表示, 表示 的欧拉函数。

的值为小于等于 且与 互质的数的个数(包含1)。

性质

对于素数 .

除了 都是偶数.

为正整数, .

欧拉函数是积性函数.

公式法

.

.

时间复杂度 .

线性筛

线性筛|欧拉筛

欧拉定理

,那么

扩展:

模板

LuoguP5091 【模板】欧拉定理

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int L=2e7+6;

int a,m,lb,phim;
char sb[L];
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int pw(int a,int m,int p){
int res=1;
while(m){
if(m&1)res=(ll)res*a%p;
a=(ll)a*a%p,m>>=1;
}
return res;
}
int phi(int x){//求欧拉函数
int res=x;
for(int i=2;i<=x;i++){
if(x%i==0)res=res/i*(i-1);
while(x%i==0)x/=i;
}
return res;
}
int main(){
scanf("%d%d%s",&a,&m,sb+1);
lb=strlen(sb+1);
phim=phi(m);
int ans=0;
for(int i=1;i<=lb;i++){//高精度处理
ans=ans*10+sb[i]-'0';
if(ans>phim)ans=ans%phim+phim;
}
if(gcd(a,m)==1)ans%=phim;
printf("%d",pw(a,ans,m));
return 0;
}

[BZOJ3884]上帝与集合的正确用法

的值。

对于100%的数据, .

显然

根据扩展3得

出现递归结构,递归即可。

#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
ll T;

ll phi(ll a){
int res=a;
for(ll i=2;i*i<=a;i++)if(a%i==0){
res=res/i*(i-1);
while(a%i==0)a/=i;
}
if(a>1)res=res*(a-1)/a;
return res;
}
ll ksm(ll a,ll m,ll md){
ll res=1;
while(m){
if(m&1)res=res*a%md;
a=a*a%md,m>>=1;
}
return res;
}
ll f(ll a){
if(a==1)return 0;
ll pi=phi(a);
return ksm(2,f(pi)+pi,a);
}

int main(){
scanf("%lld",&T);
while(T--){
ll p;
scanf("%lld",&p);
printf("%lld\n",f(p));
}
return 0;
}