欧拉定理

欧拉函数

• 欧拉函数是小于等于 的正整数中与 互质的数的个数。

欧拉定理

• 对于任意互素的 和 ，有

参考链接

费马小定理

• 当为质数，则
  

因为

欧拉函数性质

1. 

2. 对于任何质数都有

3. 如果数(为质数),那么
   证明：
   因为数n只有p这个质因子，所以在1~中只要找出没有p这个因子的数的个数就是
   

4. 如果数,那么(欧拉函数的积性函数)

5. 任意一个大于的正整数都可以分解一系列质数的积的形式如：
   (其中都是质数)
   根据欧拉函数的积性函数
   
   根据性质3
   
   所以可得
   
   所以
   

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n;
ll ol(int x)
{
    int res=x;
    ll ans=x;
    for(int i=2;i*i<=res;i++)
    {
        if(x%i==0)
        {
            ans=ans*(i-1)/i;
        }
        while(x%i==0)
        {
            x/=i;
        }
    }
    if(x>1)
    {
        ans=ans*(x-1)/x;
    }
    return ans;
}
int main( )
{
    while(~scanf("%d",&n))
    {
        printf("%lld\n",ol(n));
    }
    return 0;
}

扩展欧拉定理(欧拉降幂)

等式中的表示可以不互质
证明链接

运用:

• 当中的d=的数特别大，就要使用欧拉降幂了

洛谷P5091

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a;
char b[20000010];
ll c;
ll ol(int x)
{
    int res=x;
    ll ans=x;
    for(int i=2; i*i<=res; i++)
    {
        if(x%i==0)
        {
            ans=ans*(i-1)/i;
        }
        while(x%i==0)
        {
            x/=i;
        }
    }
    if(x>1)
    {
        ans=ans*(x-1)/x;
    }
    return ans;
}
ll pow(int a,ll n,int mod)
{
    ll ans=1;
    ll base=a;
    while(n)
    {
        if(n&1)
        {
            ans=ans*base%mod;
        }
        base=base*base%mod;
        n>>=1;
    }
    return ans%mod;
}
int main( )
{
    int flag=0;
    scanf("%d %d %s",&a,&c,&b);
    ll phi=ol(c);
    int len=strlen(b);
    ll cnt=0;
    for(int i=0; i<len; i++)
    {
        cnt=cnt*10+b[i]-'0';
        if(cnt>=phi)
        {
            flag=1;
            break;
        }
    }
    if(flag==1)
    {
        ll ans=0;
        for(int i=0; i<len; i++)
        {
            ans=(ans*10+b[i]-'0')%phi;
        }
        ans+=phi;
        printf("%lld\n",pow(a,ans,c));
    }
    else//b<φ(p)
    {
        printf("%lld\n",pow(a,cnt,c));   
    }
    return 0;
}