算法

欧拉函数

欧拉函数
对于正整数nn,欧拉函数是小于或等于nn的正整数中与nn互质的数的数目，记作φ(n)φ(n).
φ(1)=1φ(1)=1
求n的欧拉值
首先， 欧拉函数是一个积性函数，当m,nm,n互质时，φ(mn)=φ(m)∗φ(n)φ(mn)=φ(m)∗φ(n)
根据唯一分解定理知 n=pa11∗pa22∗…∗paxxn=p1a1∗p2a2∗…∗pxax
因此 φ(n)=φ(pa11)∗…∗φ(paxx)φ(n)=φ(p1a1)∗…∗φ(pxax)
对于任意一项 φ(pass)=pass−p(as−1)sφ(psas)=psas−ps(as−1)
从定义出发 φ(pass)φ(psas)等于小于或等于passpsas的正整数中与passpsas互质的数的数目

从11到passpsas中共有passpsas个数字

其中与passpsas不互质的有ps,2ps,…,psas−1∗psps,2ps,…,psas−1∗ps ,共psas−1psas−1项

所以 φ(pass)φ(psas) = passpsas - psas−1=pass∗(1−1ps)psas−1=psas∗(1−1ps)
因此
φ(n)=φ(pa11)∗…∗φ(paxx)
φ(n)=φ(p1a1)∗…∗φ(pxax)
=(pa11−p1a1−1)∗…∗(paxx−pxax−1)
=(p1a1−p1a1−1)∗…∗(pxax−pxax−1)
=pa11∗(1−1p1)∗pa22∗(1−1p2)∗…∗paxx∗(1−1px)
=p1a1∗(1−1p1)∗p2a2∗(1−1p2)∗…∗pxax∗(1−1px)
=pa11∗pa22∗…∗paxx∗(1−1p1)∗(1−1p2)∗…∗(1−1px)
=p1a1∗p2a2∗…∗pxax∗(1−1p1)∗(1−1p2)∗…∗(1−1px)
=n∗∏i=1x(1−1pi)

欧拉函数的常用性质：

1.如果n,m互质，则ϕ(nm)=ϕ(n)ϕ(m)1.如果n,m互质，则ϕ(nm)=ϕ(n)ϕ(m);
2.小于等于n，且与n互质的数的和是ϕ(n)×n/22.小于等于n，且与n互质的数的和是ϕ(n)×n/2;
3.欧拉定理：如果n,a互质，且均为正整数，则aϕ(n)≡1(modn)3.欧拉定理：如果n,a互质，且均为正整数，则aϕ(n)≡1(modn);
欧拉函数代码

int phi(int x)
{
    int res = x;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        {
            res = res / i * (i - 1);
            while (x % i == 0) x /= i;
        }
    if (x > 1) res = res / x * (x - 1);

    return res;
}

C++ 代码

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int x,res;
        cin>>x;
        res=x;
        for(int i=2;i<=x/i;i++)
        {
            if(x%i==0)
            {
                while(x%i==0)
                    x/=i;
                res=res/i*(i-1);
            }
        }
        if(x>1) res=res/x*(x-1);
        cout<<res<<endl;
    }
}