欧拉函数_牛客博客

一、互质：
若gcd(a,b)=1,则称a,b互质。
若gcd(a,b,c)=1,则称a,b,c互质。
若gcd(a,b)=gcd(a,c)=gcd(b,c)=1,则称a,b,c两两互质。

二、欧拉函数：
1。1–N中与N互质的数的个数被成为欧拉函数。记为 $φ (N)$ 。
2。通式： $φ (N) = N * （ 1 - 1 / p 1) * (1 - 1 / p 2) \dots \dots （ 1 - 1 / p m ）$
其中p1…pm为唯一分解后的质因子。
唯一分解时顺便求出欧拉函数。
特别的 $φ （ 1 ） = 1$ 。

int P(int n)
{
    int k=n;
    for(int i=0;i<cnt&&prime[i]*prime[i]<=n;i++)
    {

        if(n%prime[i]==0)
        {
            k=k-k/prime[i];//k=k/prime[i]*(prime[i]-1)
            while(!(n%prime[i])) n/=prime[i];
        }
    }
    if(n>1) k=k-k/n;//k=k/n*(n-1)
    return k;
}

三、欧拉函数的性质：
1。对于质数p： $φ （ p ） = p - 1$ 。

2。若p为质数， $φ （ p^{k} ） = p^{k} - p^{k - 1}$ 。

3。1–N中与N互质的数的和为 $n * φ （ n ） / 2$ 。

4。若a，b互质 $φ （ a b ） = φ （ a ） φ （ b ）$ 。
特别的： $n 为奇（奇质）数时， φ （ 2 n ） = φ （ n ）$ 。

5。 $φ （ n ） = φ （ p 1^{c 1} ） φ （ p 2^{c 2} ） \dots \dots φ （ p m^{c m} ）$

6。n＞2时，φ（n）为偶数。

7。n的因数的欧拉函数之和为n。

8。设p为质数，若p|n且p² |n，则 $φ （ n ） = φ （ n / p ） * p$ 。
设p为质数，若p|n且p² 不整除n，则 $φ （ n ） = φ （ n / p ） \times （ p - 1 ）；即 φ （ n ） = φ （ n / p ） \times φ （ p ）$ 。

9。若已知欧拉函数值n，求最小的x满足φ（x）≥n。
则x为＞n的最小的素数（≥n+1的最小的素数）。

四、打表求欧拉函数：
1。Eratosthenes筛法：

void euler(int n)
{
    phi[1]=1;//hpi[1]=0;
    for(int i=2;i<=n;i++) phi[i]=i;
    for(int i=2;i<=n;i++)
    {
        if(phi[i]==i)
        {
            for(int j=i;j<=n;j+=i)
                phi[j]=phi[j]/i*(i-1);
        }
    }
    return ;
}

2。欧拉筛法：
一、

int v[maxn],prime[maxn],phi[maxn];
int cnt=0;
void euler(int n)
{
    memset(v,0,sizeof(v));
    phi[1]=1;//phi[1]=0;
    for(int i=2;i<=n;i++)
    {
        if(v[i]==0)
        {
            v[i]=i;
            prime[cnt++]=i;
            phi[i]=i-1;
        }
        for(int j=0;j<m;j++)
        {
            if(prime[j]>v[i]||prime[j]>n/i) break;
            v[i*prime[j]]=prime[j];
            phi[i*prime[j]]=phi[i]*(i%prime[j]?prime[j]-1:prime[j]);
        }
    }
    return ;
}

二、

int p[maxn],prime[maxn];
bool ha[maxn]=false;
int cnt=0;
void Prime(int n)
{
    p[1]=1;//p[1]=0;
    for(int i=2;i<=n;i++)
    {
        if(!ha[i])
        {
            prime[cnt++]=i;
            p[i]=i-1;
        }
        for(int j=0;j<cnt&&prime[j]<=n/i;j++)
        {
            ha[i*prime[j]]=true;
            if(i%prime[j]==0)
            {
                p[i*prime[j]]=p[i]*prime[j];
                break;
            }
            else p[i*prime[j]]=p[i]*p[prime[j]];
        }
    }
    return ;
}