Euler function

• Euler function $\phi (n)$ ： No more than $n$ And with the $n$ The number of reciprocal positive integers ,$n\in N^{\ast }$
• $p$ Prime number $\iff \phi (p)=p-1$
• $p$ Prime number ,$a\in N^{\ast }\Rightarrow \phi \left(p^a\right)=p^a-p^{a-1}$
  • prove ： And $p^a$ Not mutually prime only $p,2p,3p,\cdots ,p^{k-1}p$ , Sum and subtract in equal proportion
• Arbitrary positive integer $n$ The prime power decomposition of $n=p_1^{a_1}\cdot p_2^{a_2}\cdots p_s{}^{a_s}\Rightarrow \phi (n)=n\cdot \left(1-\frac{1}{p_1}\right)\cdot \left(1-\frac{1}{p_2}\right)\cdots \left(1-\frac{1}{p_s}\right)$
  • prove ： It can also be written as $\phi \left(p^a\right)=p^a(1-\frac{1}{p})$ , The above formula can be obtained from the fact that Euler function is an integral function .
  • inference ： When $n$ In an odd number of , Yes $\phi (2n)=\phi (n)$
• $n>2,n\in N^{\ast }\Rightarrow \phi (n)$ It's even
• $n\in N^{\ast },{\sum }_{d\mid n}\phi (d)=n$
• Euler theorem ： $m$ Is a positive integer , $a$ Is an integer $(a,m)=1$, that $a^{\phi (m)}\equiv$ $1(\mathrm{m}\mathrm{o}\mathrm{d}m)$
• $x\mathrm{m}\mathrm{o}\mathrm{d}p=0\Rightarrow \phi (xp)=\phi (x)\cdot p$ , Prove the following ：
  • $[1,x]$ China and $x$ Non coprime numbers $y$ ,$y+x$ And $x$ Still not coprime ,$y+cx,c\le p$ Still with $x$ Not mutual , namely $[1,x]$ And... In the interval $x$ Non coprime numbers are in $+cx$ Still not reciprocal after . The properties of the preceding prime numbers can be proved $[1,x]$ China and $x$ Coprime numbers are in $+cx$ Still coprime after . So we can get the above conclusion .

notes ： The following are from kuangbin The template of

Decomposition prime factor method

int Euler(int n)
{
    
    getFactors(n); //  The decomposition quality factor mentioned earlier 
    int ret = n;
    for (int i = 0; i < fatCnt; i++)
        ret = ret / factor[i][0] * (factor[i][0] - 1);
    return ret;
}

Recurrence method

take $\phi (i)$ Set first as $i$ , hold $ki$ Original $\phi$ Take this $i$ Contribution .

In the process ,$\phi$ No assignment indicates that it is a prime number

int euler[N];
void getEuler()
{
    
    memset(euler, 0, sizeof(euler));
    euler[1] = 1;
    for (int i = 2; i < N; i++)
        if (!euler[i])
            for (int j = i; j < N; j += i)
            {
    
                if (!euler[j])
                    euler[j] = j;
                euler[j] = euler[j] / i * (i - 1);
            }
}

Find a single Euler function

Look for the prime factor , Use formula

int euler(int n)
{
    
    int ans = n;
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0)
        {
    
            ans -= ans / i;
            while (n % i == 0)
                n /= i;
        }
    if (n > 1)
        ans -= ans / n;
    return ans;
}

Linear sieve

bool check[N + 10];
int phi[N + 10];
int prime[N + 10];
int tot; // The number of primes 
void phi_and_prime_table(int N)
{
    
    memset(check, false, sizeof(check));
    phi[1] = 1;
    tot = 0;
    for (int i = 2; i <= N; i++)
    {
    
        if (!check[i])
        {
    
            prime[tot++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; j < tot; j++)
        {
    
            if (i * prime[j] > N)
                break;
            check[i * prime[j]] = true;
            if (i % prime[j] == 0)
            {
    
                phi[i * prime[j]] = phi[i] * prime[j]; //  Utilization property 
                break;
            }
            else
                phi[i * prime[j]] = phi[i] * (prime[j] - 1); //  Integrability function 
        }
    }
}