欧拉函数小结

概念

欧拉函数用希腊字母φ表示,φ(N)表示N的欧拉函数

对φ(N)的值,我们可以通俗地理解为小于N且与N互质的数的个数(包含1).

---

性质

1、对于素数p, φ(p)=p-1

2、对一个正整数N分解质因数 N=（P1^q1）*（P2^q2）*...*（Pn^qn）则 φ(N)=N * (1 - 1/P1) * (1 - 1/P2) * ... * (1-1/Pn)

---

 分解质因数模板

//分解质因数和求一个数的欧拉函数
void init(ll n)
{
    // int ans=x;
    for(ll i=2;i*i<=n;i++)
    {
        if(n&&n%i==0)
        {
            //ans=ans-ans/i;
            while(n%i==0)
            {
                n/=i;
            }
            s.insert(i);
        }
    }
    if(n>1) ans=ans-ans/n,s.insert(n);
    // return ans;
}

线性筛法 --- 用于单个数求欧拉函数

int Euler(int n)
{
    int ans=n;
    for(int i=0;i<cnt&&prime[i]<=n;i++)
    {
        if(n%prime[i]==0)
        {
            ans=ans-ans/prime[i];
            while(n%prime[i]==0)
                n/=prime[i];
        }
    }
    if(n==1)
        return ans;
    if(n>1)
        return ans-ans/n;
 
}

筛选法（基于素数筛） --- 求1~N所有的欧拉函数

void Init()
{
     for(int i=1;i<N;i++)
       euler[i]=i;
     for(int i=2;i<N;i++)                 //i=1时，euler[1] 不变
        if(euler[i]==i)
           for(int j=i;j<N;j+=i)
              euler[j]=euler[j]/i*(i-1);
}