欧拉函数

欧拉函数的公式可以用容斥原理证明。

欧拉函数的求法1：O(n*sqrt(n))

ACWING873欧拉函数
给定 n 个正整数 ai ，请你求出每个数的欧拉函数。

欧拉函数的定义

输入格式
第一行包含整数 n 。

接下来 n 行，每行包含一个正整数 ai 。

输出格式
输出共 n 行，每行输出一个正整数 ai 的欧拉函数。

数据范围
1≤n≤100 ,
1≤ai≤2×109
输入样例：

3
3
6
8

输出样例：

2
2
4

AC代码：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,a,res;
    cin>>n;
    while(n--)
    {
        cin>>a;
        res=a;
        for(int i=2;i<=a/i;i++)
        {
            if(a%i==0)
            {
                res=res/i*(i-1);
                while(a%i==0)a=a/i;
            }
        }
        if(a>1)res=res/a*(a-1);
        cout<<res<<'\n';
    }
    return 0;
}

注意点：

• 用到了试除法
• res=res/i*(i-1);可以避免出现小数，影响计算结果。

欧拉函数求法2：线性筛法 O(n)

给定一个正整数 n ，求 1∼n 中每个数的欧拉函数之和。

输入格式
共一行，包含一个整数 n 。

输出格式
共一行，包含一个整数，表示 1∼n 中每个数的欧拉函数之和。

数据范围
1≤n≤106
输入样例：

6

输出样例：

12

AC代码：

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int st[N],primes[N],phi[N],cnt;
void get_eulers(int n)
{
    phi[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!st[i])
        {
            primes[cnt++]=i;
            phi[i]=i-1;
        }
        for(int j=0;primes[j]<=n/i;j++)
        {
            st[primes[j]*i]=1;
            if(i%primes[j]==0)
            {
                phi[primes[j]*i]=phi[i]*primes[j];
                break;
            }
            phi[primes[j]*i]=phi[i]*(primes[j]-1);
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    long long res;
    cin>>n;
    get_eulers(n);
    for(int i=1;i<=n;i++)res+=phi[i];
    cout<<res;
    return 0;
}

注意点：

• 本题用的是线性筛法，模板在线性筛模板上做了一些调整。
• phi数组的计算分4中情况讨论。
  情况1：phi[1]时，表示1中的欧拉函数，其值就是1，直接赋值即可。
  情况2：phi[i]的i为质数时，则1~i-1的所有数都和i互质，所以phi[i]=i-1。
  情况3：pj（primes[j]的简称）是i的质因子。此时， phi[primes[j]*i]=phi[i]*primes[j];(可根据欧拉函数的公式推）
  情况4：pj不是i的质因子。此时， phi[primes[j]*i]=phi[i]*(primes[j]-1);

欧拉定理和费马定理

了解一下，无代码