【学习笔记】欧拉函数

定义

对于正整数 n,其欧拉函数为小于等于 n 的正整数中与 n 互质的数的个数,记为 \varphi(n)

性质与定理

基本性质

p 为任意素数,则有以下性质:

  1. \varphi(p)=p-1
  2. \varphi(p^k)=(p-1)p^{k-1},其中 k 为任意大于等于1的整数
  3. \varphi(ab)=\varphi(a)\cdot\varphi(b),其中 a,b 互质,即 \mathrm{gcd}(a,b)=1

以下为证明:

性质1:显然。

性质2:将 1\dots p^k 拆分为 p^{k-1} 段,每段包含 p 个数。显然每段中只有一个数与 p 不互质,总的与 p 互质的数的个数即为 (p-1)p^{k-1},得证。

性质3:设 A,B,C 是分别与 a,b,ab 互质的集,根据中国剩余定理(CRT),A\times B 可与 C 建立双射(一一映射),因此与 ab 互质的数的个数为 \varphi(a)\cdot\varphi(b)。以下为详细说明:

a,b 可分解为若干素因子幂之积:
a=\prod_{i=1}^n p_i^{k_i}=p_1^{k_1}\cdots p_n^{k_n}\\ b=\prod_{i=1}^m q_i^{t_i}=q_1^{t_1}\cdots q_n^{t_m}
ab 可分解为:
ab=\prod_{i=1}^n p_i^{k_i}\cdot\prod_{i=1}^m q_i^{t_i}=p_1^{k_1}\cdots p_n^{k_n}q_1^{t_1}\cdots q_n^{t_m}
并且由于 a,b 互质,其素因子集不相交,即 \lbrace p_i\rbrace\cap\lbrace q_i\rbrace=\varnothing

设有 x\in A,y\in B,z\in C,由中国剩余定理,设:
\begin{cases} x\equiv r_{a1}\pmod{p_1^{k_1}}\\ \cdots\\ x\equiv r_{an}\pmod{p_n^{k_n}}\\ \end{cases}\quad \begin{cases} y\equiv r_{b1}\pmod{q_1^{t_1}}\\ \cdots\\ y\equiv r_{bm}\pmod{q_m^{t_m}}\\ \end{cases}
显然,在模 a 意义下的 x 与余数序列 r_{a1}\dots r_{an} 一一对应;同样,在模 b 意义下的 y 与余数序列 r_{b1}\dots r_{bm} 一一对应

令:
\begin{cases} z\equiv r_{a1}\pmod{p_1^{k_1}}\\ \cdots\\ z\equiv r_{an}\pmod{p_n^{k_n}}\\ z\equiv r_{b1}\pmod{q_1^{t_1}}\\ \cdots\\ z\equiv r_{bm}\pmod{q_m^{t_m}}\\ \end{cases}
显然,对于给定的余数序列 r_{a1}\dots r_{an},r_{b1}\dots r_{bm}z 在模 ab 意义下存在且唯一,由此可建立双射关系,得证

欧拉定理

a,n 互质,则有:
a^{\varphi(n)}\equiv 1\pmod{n}
这就是欧拉定理

顺便一提,费马小定理其实是欧拉定理当 n 为质数时的特例

扩展欧拉定理(降幂公式)

a^b\equiv\begin{cases} a^{b\bmod\varphi(p)},&\mathrm{gcd}(a,p)=1\\ a^b,&\mathrm{gcd}(a,p)\ne 1,b<\varphi(p)\\ a^{b\bmod\varphi(p)+\varphi(p)},&\mathrm{gcd}(a,p)\ne 1,b\ge\varphi(p)\\ \end{cases}\pmod{p}

在不容易判定 a,p 是否互质时,可用以下公式

b\ge\varphi(p) 时:
a^b\equiv a^{b\bmod\varphi(p)+\varphi(p)}\pmod{p}

求解

单个欧拉函数值的求解

n 可分解为 n=\prod_{i=1}^m p_i^{k_i},则 n 的欧拉函数值为:
\varphi(n)=n\prod_{i=1}^m (1-\frac{1}{p_i})
证明:
\begin{aligned}\varphi(n)&=\prod_{i=1}^m \varphi(p_i^{k_i})\\&=\prod_{i=1}^m (p_i-1)p_i^{k_i-1}\\&=\prod_{i=1}^m (1-\frac{1}{p_i})p_i^{k_i}\\&=\prod_{i=1}^m p_i^{k_i}\cdot\prod_{i=1}^m(1-\frac{1}{p_i})\\&=n\prod_{i=1}^m(1-\frac{1}{p_i})\end{aligned}

单个欧拉函数值求解的复杂度为 O(\sqrt{n}),即试除法分解质因子的复杂度

线性筛法

线性筛法需要用到以下结论。若 p 为素数,k 为任意正整数,则:

  1. \varphi(p)=p-1
  2. k\bmod p=0 时,\varphi(kp)=p\cdot\varphi(k)
  3. k\bmod p\ne 0 时,\varphi(kp)=(p-1)\cdot\varphi(k)

证明:

结论1:即性质1

结论2:当 k\bmod p=0 时,显然 kkp 的质因子集相同,且其分解形式仅有等于 p 的那个质因子的指数不同且相差1:
k=p_1^{k_1}\cdots p_i^{k_i}\cdots p_m^{k_m}\\ kp=p_1^{k_1}\cdots p_i^{k_i+1}\cdots p_m^{k_m}
其中 p_i=p

所以:
\begin{aligned} \varphi(kp)&=kp\prod_{i=1}^m p_i^{k_i}\\ &=p\cdot(k\prod_{i=1}^m p_i^{k_i})\\ &=p\cdot\varphi(k) \end{aligned}
结论3:当 k\bmod p\ne 0 时,显然有 \mathrm{gcd}(k,p)=1,根据欧拉函数的积性性质可得:
\varphi(kp)=\varphi(p)\cdot\varphi(k)=(p-1)\cdot\varphi(k)
在线性筛素数时,可以顺便将欧拉函数筛出,总复杂度 O(n)

Code

Luogu P2158 [SDOI2008]仪仗队

线性筛法:

#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 40005
#define int long long

using namespace std;

int n, tot = 0;
int phi[MAX_N];
int pri[MAX_N];
bool vis[MAX_N];

void getphi(int n) {
    vis[0] = vis[1] = true;
    phi[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) {
            pri[++tot] = i;
            phi[i] = i - 1;
        }
        for (int j = 1; j <= tot && i * pri[j] <= n; j++) {
            vis[i * pri[j]] = true;
            if (!(i % pri[j])) {
                phi[i * pri[j]] = pri[j] * phi[i];
                break;
            }
            phi[i * pri[j]] = (pri[j] - 1) * phi[i];
        }
    }
}

signed main() {
    scanf("%lld", &n);
    if (n == 1) {
        printf("0\n");
        return 0;
    }
    getphi(n);
    int ans = 0;
    for (int i = 1; i < n; i++) {
        ans += phi[i];
    }
    printf("%lld\n", (ans << 1) + 1);
}

单个欧拉函数值求解:

#include <iostream>
#include <stdio.h>
#include <string.h>
#define int long long

using namespace std;

int n;

int getphi(int x) {
    int ans = x, t = x;
    for (int i = 2; i * i <= x; i++) {
        if (!(t % i)) {
            ans = ans / i * (i - 1);
            while (!(t % i)) {
                t /= i;
            }
        }
    }
    if (t != 1) {
        ans = ans / t * (t - 1);
    }
    return ans;
}

signed main() {
    scanf("%lld", &n);
    if (n == 1) {
        printf("0\n");
        return 0;
    }
    int ans = 0;
    for (int i = 1; i < n; i++) {
        ans += getphi(i);
    }
    printf("%lld\n", (ans << 1) + 1);
}

Luogu P5091 【模板】扩展欧拉定理

#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 20000005
#define int long long

using namespace std;

int n, a, p;
char s[MAX_N];

int getphi(int x) {
    int ans = x, t = x;
    for (int i = 2; i * i <= x; i++) {
        if (!(t % i)) {
            ans = ans / i * (i - 1);
            while (!(t % i)) {
                t /= i;
            }
        }
    }
    if (t != 1) {
        ans = ans / t * (t - 1);
    }
    return ans;
}

int fpow(int x, int k) {
    int ans = 1;
    while (k) {
        if (k & 1) {
            ans = ans * x % p;
        }
        x = x * x % p, k >>= 1;
    }
    return ans;
}

signed main() {
    scanf("%lld%lld%s", &a, &p, s + 1);
    n = strlen(s + 1);
    int phi = getphi(p), b = 0;
    for (int i = 1; i <= n; i++) {
        b = b * 10 + s[i] - '0';
        if (b >= phi) {
            b = b % phi + phi;
        }
    }
    printf("%lld\n", fpow(a, b));
}
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注