数学笔记:数论

数学笔记:数论

欧拉函数(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) = 1a^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(完全积性)

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

参考资料



发表回复

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

This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据