定义
对于正整数 n，其欧拉函数为小于等于 n 的正整数中与 n 互质的数的个数，记为 \varphi(n)
性质与定理
基本性质
设 p 为任意素数，则有以下性质：
- \varphi(p)=p-1
- \varphi(p^k)=(p-1)p^{k-1}，其中 k 为任意大于等于1的整数
- \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 为任意正整数，则：
- \varphi(p)=p-1
- 当 k\bmod p=0 时，\varphi(kp)=p\cdot\varphi(k)
- 当 k\bmod p\ne 0 时，\varphi(kp)=(p-1)\cdot\varphi(k)
证明：
结论1：即性质1
结论2：当 k\bmod p=0 时，显然 k 与 kp 的质因子集相同，且其分解形式仅有等于 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
线性筛法：
#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);
}
#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));
}