欧拉函数

定义

欧拉函数即 φ(n)\varphi(n)，表示的是小于等于 nn 和 nn 互质的数的个数。
φ(1)=1\varphi(1) = 1。当 nn 是质数的时候，有 φ(n)=n−1\varphi(n) = n - 1。

性质

欧拉函数是积性函数。

n=∑d∣nφ(d)n = \sum_{d \mid n}{\varphi(d)} 。

$ \varphi(n) = n \prod (1 - \frac{1}{p_i}) $。

单点计算

UVA10179 Irreducable Basic Fractions

本题由于 nn 范围极大，需要单点计算。

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

O(N) 批量计算

洛谷 P2398 GCD SUM

∑i=1n∑j=1ngcd⁡(i,j)\sum_{i=1}^{n} \sum_{j=1}^{n} \gcd(i,j)

=∑i=1n∑j=1n∑d∣gcd⁡(i,j)ϕ(d)= \sum_{i=1}^{n} \sum_{j=1}^{n} \sum_{d \mid \gcd(i,j)} \phi(d)

=∑i=1n∑j=1n∑d∣i,d∣jϕ(d)= \sum_{i=1}^{n} \sum_{j=1}^{n} \sum_{d \mid i, d \mid j} \phi(d)

=∑i=1n∑j=1n∑d=1nϕ(d)[d∣i][d∣j]= \sum_{i=1}^{n} \sum_{j=1}^{n} \sum_{d=1}^{n} \phi(d) [d \mid i] [d \mid j]

=∑d=1nϕ(d)∑i=1n∑j=1n[d∣i][d∣j]= \sum_{d=1}^{n} \phi(d) \sum_{i=1}^{n} \sum_{j=1}^{n} [d \mid i] [d \mid j]

=∑d=1nϕ(d)⌊nd⌋2= \sum_{d=1}^{n} \phi(d) \left\lfloor \frac{n}{d} \right\rfloor^2 

int n,isp[N],phi[N];
vector<int> primes;
void get_phi(){
    for(int i=2;i<=n;i++)isp[i]=1;
    phi[1]=1;
    for(int i=2;i<=n;i++){
        if(isp[i]){
            primes.push_back(i);
            phi[i]=i-1;
        }
        for(int p:primes){
            if(i*p>n)break;
            isp[i*p]=0;
            if(i%p==0){ //i的质因数分解中已经包含了p，由phi(n)=n*∏(1-1/p_i)，phi[i*p]=phi[i]*p
                phi[i*p]=phi[i]*p;
                break;
            }else{      //互质，利用欧拉函数的积性
                phi[i*p]=phi[i]*phi[p];
            }
        }
    }
}

这是线性筛法求欧拉函数，在用线性筛法找出每个数的最小质因数的同时，利用欧拉函数的积性性质，递推出每个数的欧拉函数值。
时间复杂度 O(n)\text{O}(n) 。

一些题目

洛谷P2215 莎拉公主的困惑

题意：求 [1,N!][1,N!] 中与 M!M! 互质的数的个数。答案模质数 RR 。M<N<107M<N<10^7 。

由 gcd⁡(a,b)=gcd⁡(a,b+ka)\gcd(a,b)=\gcd(a,b+ka)，可知

ans=n!m!φ(m!)\text{ans} = \frac{n!}{m!}\varphi(m!)

=n!m!×m!∏p是m的质因子p−1p= \frac{n!}{m!} \times m! \prod\limits_{p是m的质因子}\frac{p-1}{p}

=n!∏p∈Pm(p−1)∏p∈Pmp=n!\frac{\prod\limits_{p\in\mathbb{P}}^{m}(p-1)}{\prod\limits_{p\in\mathbb{P}}^{m}p}

然而 ∏p∈Pmp\prod\limits_{p\in\mathbb{P}}^{m}p 可能包含因子 RR ，此时其逆元不存在，但 n!n! 也必然有因子 RR，故需要同时约去一个 RR 之后可以正确计算。若 N≥RN \ge R 且 M<RM < R 则 ans=0\text{ans}=0 。

本题由于空间限制不能 #define int long long，需要在涉及乘法运算的时候加上 1LL * ... 来避免溢出。

submission

欧拉定理