前置知识：

欧拉函数：质数相关，约数相关

欧拉定理：同余，简化剩余系

详情可见 OI wiki

---

定义 $1 \sim N$ 中和 $N$ 互质的数个数称欧拉函数，记作 $\varphi(N)$

单个欧拉函数求解：

$\varphi(N) = N \times \prod_{p \mid n} (\frac{p-1}{p})~~$ 其中p是质数

证明

容斥原理，设 $p,q$ 分别是 $N$ 的质因子

则要筛掉 $N / p$ 和 $N / q$ 个数，并且 $p*q$ 及倍数算了两次，还要加上 $N / (p*q)$ 个

所以 $N - \frac{N}{p} - \frac{N}{q} + \frac{N}{pq} = N \times \frac{p-1}{p} \times \frac{q-1}{q}$

欧拉函数性质定理

1. $\forall n > 1 , 1 \sim n$ 和 n 互质的数的和为 $n \times \varphi(n) /2$

证明1

$\gcd(a,b) = gcd(a,a-b)$ 所以和 $n$ 互质的数成对出现，平均值为 $n / 2$

互质的数个数为 $\varphi(n)$

1. $\varphi(n)$ 是积性函数，也就是对于 $a,b$ 互质，有 $\varphi(ab)=\varphi(a) \times \varphi(b)$,该定理由分解质因数得到

2. $\sum_{p \mid n} \varphi(p) = n$

3. 若 $p$ 为质数，$p \mid n$ 且 $p^2 \mid n$ ， 有 $\varphi(n) = \varphi(n/p) \times p$

4. 若 $p$ 为质数，$p \mid n$ 且 $p^2 \nmid n$ ， 有 $\varphi(n) = \varphi(n/p) \times (p-1)$

证明3,4

$p \mid n$ 且 $p^2 \mid n$，则 $p , n/p$ 质因子种类相同，计算 $\varphi(n) \div \varphi(n/p) = p$

$p \mid n$ 且 $p^2 \nmid n$，则 $p , n/p$ 互质，根据 定理2，$\varphi(n) = \varphi(n/p) \times \varphi(p) =\varphi(n/p) \times (p-1)$

运用性质3,4，可以在 $O(n)$ 时间计算 $\varphi(2 \sim n)$

在线性素数筛中直接计算即可

code

void cal_pri(int x)
{
    for(int i=2;i<=x;i++)
    {
        if(!v[i])
        {
            v[i]=i;
            pri[++top]=i;
            phi[i]=i-1;
        }
        for(int j=1;j<=top&&i*pri[j]<=x;j++)
        {
            if(pri[j]>v[i]) break;
            v[i*pri[j]]=pri[j];
            phi[i*pri[j]]=phi[i]*(i%pri[j]?pri[j]-1:pri[j]);
        }
    }
}

欧拉定理

若 $n,p$ 互质，则 $n^{\varphi(p)} \equiv 1 ~ (mod ~ p)$

证明

设 $n$ 的简化剩余系为 $\{\overline{a_1} , \overline{a_2} , ... , \overline{a_{\varphi(n)}} \}$

对于 $\forall a_i,a_j$ , 有 $n * a_i \equiv n* a_j (mod ~ p)$ , 移项得 $n * (a_i - a_j) \equiv 0 (mod ~ p)$

因为 $n,p$ 互质，所以 $a_i - a_j \equiv 0$ , 进而 $a_i \equiv a_j$

因为简化剩余系模p乘法封闭，$n,p$ 互质，所以 $\forall a_i ,n * a_i$也属于 n 的简化剩余系

所以：

$n^{\varphi(p)} a_1a_2...a_{\varphi(n)} \equiv (aa_1)(aa_2)...(aa_{\varphi(n)}) \equiv a_1a_2...a_{\varphi(n)} (mod ~ p)$

由此得到费马小定理：(同时乘a)

p是质数，则对于任意整数 $a$ , $a^p \equiv a (mod ~ p)$

欧拉定理的扩展

1. 若 $a,p$ 互质， 则对于任意整数 $b$ ，有 $a^b \equiv a ^ {b ~ mod ~ \varphi(p)} ~ (mod ~ p)$

2. 若 $a,p$ 不互质，对于整数$b \geq \varphi(p)$，有 $a^b \equiv a ^ {(b ~ mod ~ \varphi(p) ~ )+\varphi(p)} ~ (mod ~ p)$

定理1证明

b可表示为 $k \times \varphi(p) + r , r \in [0,\varphi(p) ~ )$ , 得 $r = b ~ mod ~ \varphi(p)$

于是 $a^b \equiv a ^ {k \times \varphi(p) + r} \equiv (a ^ {\varphi(p)} ) ^ k \times a^r \equiv 1^k \times a^r \equiv a ^ {b ~ mod ~ \varphi(p)} ~ (mod ~ p)$

例题：

UVA11327 Enumerating Rational Numbers

hint

每一个大于1的数贡献为 $\varphi(a)$ , 掐指一算

前20000位欧拉函数的和正好为12158598919，可以在很快时间内枚举出来

---

[POJ3696] The Luckiest number

hint

$x$ 个 8 可以写成 $8(10^x-1)/9$

$L \mid \frac{8(10^x-1)}{9}$ 等同于 $9L \mid 8(10^x-1)$

设 $d=\gcd(9L,8)$

可以得到 $\gcd(\frac{9L}{d},\frac{8}{d})=1$

所以 $\frac{9L}{d},\frac{8(10^x-1)}{d}$ 的共同因数存在于 $\frac{9L}{d}$ 和 $10^x-1$中

所以得出 $10^x \equiv 1 ~ (mod ~ \frac{9L}{d})$

若 $\gcd(10,\frac{9L}{d}) \not =1$ , 则模运算一定不等于1,则无解

设 $x_0$ 为 使得式子成立的最小解，那么 $10^{x_0} \equiv 1 ~ (mod ~ \frac{9L}{d})$ , 于是 $10^{kx_0} \equiv 1 ~ (mod ~ \frac{9L}{d})$

根据欧拉定理，$10^{\varphi(p)} \equiv 1 ~ (mod ~ p)$ , 所以 $x_0$ 是 $\varphi(p)$ 的约数

参考资料

1. OI wiki (欧拉函数，欧拉定理 & 费马小定理) ， 详情
2. 算法竞赛进阶指南(0x33同余)