欧拉函数 | 欧拉定理

摘要

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

欧拉函数

定义

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

的值为小于等于 且与 互质的数的个数 (包含 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 上帝与集合的正确用法

的值,多组数据, .

显然

根据扩展 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;
}

  目录