算法竞赛笔记.欧拉函数与欧拉定理

,

定义

欧拉函数即 φ(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

欧拉定理

若 gcd⁡(a,m)=1\gcd (a,m)=1 ，则有 aφ(m)≡1(modm)a^{\varphi(m)} \equiv 1 \pmod m 。

扩展欧拉定理

对于任意正整数 mm、整数 aa 和非负整数 kk，有

ak≡{ak mod φ(m),gcd⁡(a,m)=1,ak,gcd⁡(a,m)≠1,k<φ(m),a(k mod φ(m))+φ(m),gcd⁡(a,m)≠1,k≥φ(m).(modm)a^k \equiv \begin{cases} a^{k \bmod \varphi(m)}, &\gcd(a,m) = 1, \\ a^k, &\gcd(a,m)\ne 1, k < \varphi(m), \\ a^{(k \bmod \varphi(m)) + \varphi(m)}, &\gcd(a,m)\ne 1, k \ge \varphi(m). \end{cases} \pmod m

欧拉定理是扩展欧拉定理在 gcd⁡(a,m)=1\gcd(a,m)=1 且 k=φ(m)k=\varphi(m) 的特殊情形。