欧拉函数（Eular’s Totient Function）

定义

在数论中，对正整数n，欧拉函数\varphi(n)是小于或等于n的正整数中与n互质的数的数目。
规定：\varphi(1) = 1

费马小定理（Fermat’s Little Theorem）

若a是一个整数，p是一个质数，则
a^{p-1} \equiv 1 \ (mod \ p)

欧拉定理（Eular’s Theorem (Number Theory)）

若n，a为正整数，且gcd(n, a) = 1，则
a^{\varphi(n)} \equiv 1 \ (mod \ n)

欧拉函数值的求解

直接公式求解

欧拉函数的值计算有以下公式
\varphi(x) = x (1 - \frac{1}{p_1}) (1 - \frac{1}{p_2}) \cdots (1 - \frac{1}{p_k})
其中p_i代表x的质因数。
因此我们可以枚举x的质因数，并计算\varphi(x)的值。
这个算法单次计算的复杂度是O(\sqrt{n})。

线性筛法求解

本方法适用于求1至n的函数值计算。
首先，我们知道欧拉函数是一个积性函数，即\varphi(nm) = \varphi(n) \varphi(m)。
对于素数，它的函数值就是它本身减1。对于非素数，我们想到了线性筛法的避免重复计算条件：prime[j]是i的一个因数。此时，我们已经知道了\varphi(prime[j])和\varphi(i)，那么可以算出\varphi(i \cdot prime[j]) = \varphi(i) \varphi(prime[j])。
这个算法的复杂度是O(n)。
代码实现如下：

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

阶（Order）

定义

若a，p为正整数，且gcd(a, p) = 1，称满足a^r \equiv 1 \ (mod \ p)的最小正整数r为a模p的阶，记作Ord_p(a)。

常用性质

1. 若a，p为正整数，且gcd(a, p) = 1，r为a模p的阶，若有正整数m满足a^m \equiv 1 \ (mod \ p)，则r|m。
2. 若a，p为正整数，且gcd(a, p) = 1，r为a模p的阶，则r|\varphi(m)。
3. 若a，p为正整数，且gcd(a, p) = 1，a^i \equiv a^j \ (mod \ p)当且仅当i \equiv j \ (mod \ Ord_p(a))。

求解阶

没什么好办法，从小到大枚举r并判断是否是阶。

原根（Primitive Root）

定义

若a，p为正整数，且gcd(a, p) = 1，称满足Ord_p(a) = \varphi(p)的a叫做模p的一个原根。
注意：不是任何p都存在原根。每个素数都存在原根。

常用性质

1. 当a为m的原根时，a^0, a^1, a^2, \cdots, a^{m-1}构成了m的一个简化剩余类。
2. 模m有原根的充要条件是m=2, 4, p^n, 2p^n，其中p为奇素数，n为任意正整数。

求解原根

我们知道了上述阶的性质2，要判断某数是不是模m的原根，可以验证是否存在m-1的一个约数a满足g^a \equiv 1 \ (mod \ m)，如果有的话那么g的阶就不是m-1，则g不是模m的原根。
一般来说原根不会很大，从2开始枚举并按照上述方法判断就可以得到。
代码如下

inline int solve_g(int m) {
    // 预处理出因数 
    int fact[105], tot = 0, x = m - 1;
    for(int i = 2; i * i <= x; i++) {
        if(x % i == 0) {
            fact[tot++] = (m - 1) / i;
            while(x % i == 0) x /= i;
        }
    }
    if(x > 1) fact[tot++] = (m - 1) / x;

    // 枚举原根
    bool success;
    for(int i = 2;; i++) {
        success = true;
        for(int j = 0; j < tot; j++) {
            if(fpow(i, fact[j], m) == 1) {
                success = false;
                break;
            }
        }
        if(success) return i;
    }
}

注：代码中fpow()函数是快速幂取模。

应用：乘法换加法（取模意义下）

我们知道，任何一个小于正整数m的正整数都可以表示为原根的某次幂，那么求一个由小于m正整数组成的数列的累乘值可以转化为原根的指数求和，这样可以不用计算高精度，且由周期性还可以缩小指数的范围。

例题：[SDOI2015]序列统计

题目描述

小C有一个集合S，里面的元素都是小于M的非负整数。他用程序编写了一个数列生成器，可以生成一个长度为N的数列，数列中的每个数都属于集合S。小C用这个生成器生成了许多这样的数列。但是小C有一个问题需要你的帮助：给定整数x，求所有可以生成出的，且满足数列中所有数的乘积mod M的值等于x的不同的数列的有多少个。小C认为，两个数列{Ai}和{Bi}不同，当且仅当至少存在一个整数i，满足Ai≠Bi。另外，小C认为这个问题的答案可能很大，因此他只需要你帮助他求出答案mod 1004535809的值就可以了。

输入输出格式

输入格式：
一行，四个整数，N、M、x、|S|，其中|S|为集合S中元素个数。第二行，|S|个整数，表示集合S中的所有元素。
输出格式：
一行，一个整数，表示你求出的种类数mod 1004535809的值。

输入输出样例

输入样例#1：

4 3 1 2
1 2

输出样例#1：

8

说明

【样例说明】
可以生成的满足要求的不同的数列有(1,1,1,1)、(1,1,2,2)、(1,2,1,2)、(1,2,2,1)、(2,1,1,2)、(2,1,2,1)、(2,2,1,1)、(2,2,2,2)。
【数据规模和约定】
对于10%的数据，1<=N<=1000；
对于30%的数据，3<=M<=100；
对于60%的数据，3<=M<=800；
对于全部的数据，1<=N<=109，3<=M<=8000，M为质数，1<=x<=M-1，输入数据保证集合S中元素不重复

解释

对于本题我们需要求出数列中所有元素的乘积，我们可以应用乘法转加法得到数列乘积的原根指数，再将x处理成原根的某次幂，根据阶的性质3即可判定是否同余。
本题的完整题解参见[SDOI2015]序列统计 题解 | KSkun’s Blog。

威尔逊定理（Wilson’s theorem）

当且仅当p为素数时，有 (p-1)! \equiv -1 \pmod{p} 。

积性函数（Multiplicative function）

定义

积性函数是指一个定义域为正整数n的数论函数f(n)，有如下性质：
\begin{aligned} & f(1) = 1 \\ & f(ab) = f(a)f(b) & (a, b) = 1 \end{aligned}
如果上述性质中，不要求a、b互质，即不只a、b互质的情况下都有f(ab) = f(a)f(b)，则f(n)为完全积性函数。

常见的积性函数

• \varphi(n)：欧拉函数
• \mu(n)：莫比乌斯函数
• \mathrm{gcd}(a, k)：最大公因数（当k为定值时）
• 1(n)：常函数，定义为1(n)=1（完全积性）

更多内容可以参见积性函数 – 维基百科，自由的百科全书

参考资料

• 线性筛法求素数 – Grubbyskyer – 博客园
• 欧拉函数值求解 – 晴雨天 – 博客园
• Wolfram|Alpha: Computational Knowledge Engine
• 欧拉函数 – 维基百科，自由的百科全书
• 费马小定理 – 维基百科，自由的百科全书
• 欧拉定理 (数论) – 维基百科，自由的百科全书
• 数论阶_百度百科
• 阶与原根学习笔记 – CSDN博客
• 新知——快速数论变换 – CSDN博客
• 原根 – 维基百科，自由的百科全书
• 原根_百度百科
• 简化剩余系_百度百科
• 数论补全计划：原根 – Tony Fang
• P3321 [SDOI2015]序列统计 题解
• 积性函数 – 维基百科，自由的百科全书