欧拉函数

欧拉函数的定义

欧拉函数 ϕ(n)\phi(n) 是指从1~n中与n互质的数的个数 例如：ϕ(1)=1\phi(1) = 1, ϕ(5)=4\phi(5) = 4 , ϕ(6)=2\phi(6) = 2

朴素法求欧拉函数

若 n = ρ1α1 × ρ2α2 × ... ×ρnαn\rho_1^{\alpha_1} \ \times \ \rho_2^{\alpha_2}\ \times \ ... \ \times \rho_n^{\alpha_n}

则 ϕ(n) = n (1−1ρ1) (1−1ρ2) ... (1−1ρn)\phi(n) \ = \ n \ (1- \frac{1}{\rho_1}) \ (1- \frac{1}{\rho_2}) \ ... \ (1- \frac{1}{\rho_n})

原理：容斥原理

解释：

  1. 先吧n个数中 $\rho_1 \ , \ \rho_2 \ , \ … \ , \rho_n $ 的倍数全不去除

  2. 这时要把 $ \rho_1\rho_2 \ , \ \rho_1\rho_3 \ , \ … \ \rho_i\rho_j \ , \ … \ \rho_{n-1}\rho_n $ 这类被减去两次的数加一遍

  3. 但会发现 $ \rho_1\rho_2\rho3 \ , \ … \ , \ \rho_i\rho_j\rho_k $ 这类三被加上了三次要减去

  4. 以此类推，得到的式子为

    ϕ(n)=n−(ρ1+ρ2+ ... +ρn)+(ρ1ρ2 , ρ1ρ3 , ... ρiρj , ... ρn−1ρn)−(ρ1ρ2ρ3 , ... , ρiρjρk)\phi(n) = n - (\rho_1 + \rho_2 + \ ... \ + \rho_n) \\ + (\rho_1\rho_2 \ , \ \rho_1\rho_3 \ , \ ... \ \rho_i\rho_j \ , \ ... \ \rho_{n-1}\rho_n ) \\ - (\rho_1\rho_2\rho3 \ , \ ... \ , \ \rho_i\rho_j\rho_k)

  5. 化简后得到上面的式子

时间复杂度：时间复杂度主要由分解质因数的那步决定分解质因数的复杂度为O(n)O_{(\sqrt{n} )} 的故求一次欧拉函数的时间复杂度也就是O(n)O_{(\sqrt{n} )} 的

核心代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
int n;
cin>>n;
int ans = n;
for(int i = 2; i <= n/i; i++){
    if(n % i == 0){
        ans = ans / i * (i-1);
        while(n % i == 0){
            n /= i;
        }
    }
}
if(n > 1) ans = ans / n *(n-1);
cout<<ans<<endl;

筛法求欧拉函数

在筛法求素数的过程中间接得到欧拉函数

  1. 当 n 为素数的时候 ϕ(n)=n−1\phi(n) = n-1

  2. 当 $ n \quad mod \quad primes[ j ] = 0 $时 说明 primes[ j ]primes[ \ j \ ] 时 n的一个质因子，

    这时候我们来看 ϕ(i)\phi(i) 与 ϕ(i × primes[ j ])\phi(i \ \times \ primes[ \ j\ ]) 的关系不难发现：i × primes[ j ]i \ \times \ primes[ \ j\ ] 与 ii 的只多了一个 $ primes[ j ] $ 倍，而且 $ primes[ j ] $ 本就是 i 的一个质因子故 i × primes[ j ]i \ \times \ primes[ \ j\ ] 与 ii 有着相同的因数，只是在分解质因数后 primes[j]primes[ j ] 的指数项不同 ，

    又欧拉函数ϕ(n) = n (1−1ρ1) (1−1ρ2) ... (1−1ρn)\phi(n) \ = \ n \ (1- \frac{1}{\rho_1}) \ (1- \frac{1}{\rho_2}) \ ... \ (1- \frac{1}{\rho_n})

    与分解因数后的指数项无关，故 ϕ(i)\phi(i) 与 ϕ(i × primes[ j ])\phi(i \ \times \ primes[ \ j\ ]) 求值时只有第一项 nn 的区别

    $\Rightarrow \ \ \phi(i \ \times \ primes[ \ j\ ]) = primes[ \ j\ ] \ \times \ \phi(i) $

  3. 当 $ n \quad mod \quad primes[ j ] \ne 0 $时， 由上面的推论基础不难发现 ϕ(i)\phi(i) 与 ϕ(i × primes[ j ])\phi(i \ \times \ primes[ \ j\ ]) 在求值的过程中在第一项 n→n×peimes[ j ]n \rightarrow n \times peimes[\ j\ ] 而因数部分多出一个 (1−1primes[ j ])(1-\frac{1}{primes[\ j\ ]})

    ⇒  ϕ(i × primes[ j ])=ϕ(i) × primes[ j ] × (1−1primes[ j ]) = ϕ(i) × (primes[ j ]−1)\Rightarrow \ \ \phi(i \ \times \ primes[ \ j\ ]) = \phi(i) \ \times \ primes[ \ j\ ] \ \times \ (1-\frac{1}{primes[\ j\ ]}) \ = \ \phi(i) \ \times \ (primes[ \ j\ ] - 1)

欧拉定理

若a与n互质，则有： $ a^{\phi(n)} \ \equiv \ 1 \ (mod \quad n) $

证明：参考 数论学习笔记

当n为质数时就会得到 an−1 ≡ 1 (modn)a^{n-1} \ \equiv \ 1 \ (mod \quad n) 费马定理


快速幂

二进制优化求幂法

在 Olog⁡kO_{\log{k}} 的时间复杂度内求出 $a^k \ \ mod \ \ p $ 的结果

思路：

二进制优化法：

预处理出 a20  mod  pa^{2^0} \ \ mod \ \ p ， a21  mod  pa^{2^1} \ \ mod \ \ p ，… ， a2log⁡k  mod  pa^{2^ {\log{k}}} \ \ mod \ \ p 的值

将 aka^k 对k 进行二进制展开 转化为 a2i+j+...+logka^{2^{i+j+...+log{k}}} 即可快速求得ak  mod  pa^k \ \ mod \ \ p

核心代码：

1
2
3
4
5
6
7
8
9
int qmi(int a, int k, int p){
    int ans = 1;
    while(k){
        if(k&1) ans = (LL)ans * a % p;
        k >>= 1;
        a = (LL)a * a % p;
    }
    return ans;
}

快速幂求逆元

逆元的定义：

若整数 bb ，mm 互质， 并且对于任意的整数 aa 都存在一个整数 xx 使得 ab  ≡  a × x (mod  m)\frac{a}{b} \ \ \equiv \ \ a \ \times \ x \ (mod \ \ m) 则称 xx 为 bb 的模 mm 的乘法逆元，记作 $ b^{-1} \ \ (mod \ \ m)$ 。

bb 存在关于 mm 的逆元的充要条件是 bb 与 mm 互质，当 mm 为质数时， bm−2b^{m-2} 即为 bb 的乘法逆元

当 mm 为质数时的证明：

$ \frac{a}{b} \ \equiv \ a b^{-1} \ (mod \ \ m) $

两边同乘 bb

$ a \ \equiv \ a \ b \ b^{-1}\ (mod \ \ m) $

$ \Rightarrow b \ b^{-1}\ \equiv \ 1 \ (mod \ \ m) $

又m为质数 由费马小定理可得

bm−1 ≡ 1 (mod  m)b^{m-1} \ \equiv \ 1 \ (mod \ \ m)

故当 bb 关于 mm 的乘法逆元 b−1=bm−2b^{-1} = b^{m-2}

核心代码：

1
2
3
4
5
6
7
8
//当m为质数时 (这时用p表示m)
//注意这里判断 impossible 的条件不能是 ans 是否为0 
//因为当p为2时不能判断b是否与p互质 qmi(b, p-2, p) 一定返回 1
int b, p;
scanf("%d%d",&b, &p);
int ans = qmi(b, p-2, p);
if(b % p) cout<<ans<<endl;
else cout<<"impossible"<<endl;

逆元存在的意义就是将除法取模转化为乘法取模


扩展欧几里得定理

裴蜀定理

若有一对正整数a，b ，那么一定存在非零整数x， y， 使得ax + by = gcd(a, b) 并且gcd(a, b) 是 ax + by 能得到的最小的正整数

证明：提取（ax + by）的最大公倍数 gcd(a, b) 所得正整数也一定是 gcd(a, b)的整数倍 故最小值为 gcd(a, b)

扩展欧几里得定理

证明：

  1. 先看边界状态当b = 0 时， a与0的最大公约数为a 故 a×1 + b×0=gcd(a, b)a \times 1 \ + \ b \times 0 = gcd(a, \ b) 此时 x = 1, y = 0 为一组解

  2. 看一个状态的后一个状态与当前状态，

    后一个状态：$ b\ \times\ y \ + \ (a \ \ mod \ \ b) \ \times \ x = gcd(a, \ b)$

    当前状态：$a \ \times\ x\ + \ b\ \times\ y = gcd(a,\ b) $

    现在找到后一个状态与前一个状态的区别讲后一个状态化简：

    首先 $(a \ \ mod \ \ b) = a \ - [a \ \div\ b ] \times b $ 这里的除法为整除

    $ b\ \times\ y \ + \ (a \ \ mod \ \ b) \ \times \ x$

    $ = b \ \times\ y + (a \ - [a \ \div\ b ] \times b) x$

    $ = a \ \times\ x \ +\ b\ \times\ (y\ -\ [a \ \div\ b ]\ \times\ x) $

    也就是前一个状态下求得的 xx 与 yy 值要在当前状态下成立需要将

    x→xx \rightarrow x

    y→(y − [a ÷ b] × x)y \rightarrow (y\ -\ [a \ \div\ b ]\ \times\ x)

核心代码：

1
2
3
4
5
6
7
8
9
int exgcd(int a, int b, int &x, int &y){
    if(!b){
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a%b, y, x);
    y -= a/b*x;
    return d;
}

注意这里求得的 xx 与 yy 是不唯一的

线性同余方程

描述：给定一组数据 aa , bb , mm , 对于这组数据求一个 xx , 使其满足 $a \ \times \ x \ \equiv \ b \ \ (mod \ \ m) $ 如果无解则输出impossible

将方程转换为裴蜀定理的形式

$a \ \times \ x \ \equiv \ b \ \ (mod \ \ m) $

$ \Rightarrow a \ \times \ x \ - \ b \ \equiv \ 0 \ \ (mod \ \ m) $

即 a × x − ba \ \times \ x \ - \ b 是 mm 的整数倍

即存在整数 yy 使得 $\Rightarrow a \ \times \ x \ - \ b \ = \ m \ \times \ y $

进一步 $\Rightarrow a \ \times \ x \ + \ m \ \times \ (-y) \ = \ b $

方程已转化为 裴蜀定理 的形式

并且由裴蜀定理可知 当且仅当 bb 是 gcd(a, m)gcd(a, \ m) 的整数倍时方程有解

1
2
3
4
5
6
//这里为了使结果在int范围内将 x*(b/d)与m取模 这个结论成立可以从原始方程中得到
int a, b, m, x, y;
scanf("%d%d%d", &a, &b, &m);
int d = exgcd(a, m, x, y);
if(b % d) printf("impossible\n");
else printf("%d\n", (long long)x*(b/d) % m);

中国剩余定理

中国剩余定理

描述：

$ m_1 \ ,\ m_2 \ ,\ \ …\ \ , \ m_n $ 两两互质

若有：

\left\{ \begin{array}{**lr**} \ x \ \equiv \ a_1 \ \ (mod \ \ m_1), &\\ \ x \ \equiv \ a_2 \ \ (mod \ \ m_2), &\\ \ ... &\\ \ x \ \equiv \ a_n \ \ (mod \ \ m_n), &\\ \end{array} \right.

令 M = m1m2...mnM \ = \ m_1 m_2 ... m_n , Mi = MmiM_i \ =\ \frac{M}{m_i} , Mi−1M_i^{-1} 表示 MiM_i 关于 mim_i 的逆元

则可得： $x \ =\ a_1\ M_1\ M_1^{-1}\ + \ \ a_1\ M_2\ M_2^{-1} \ +\ …\ +\ \ a_1\ M_n\ M_n^{-1} $

证明：

由逆元的性质 $M_i\ M_i^{-1} \equiv 1 \ \ (mod \ \ m_i) $

又有$ m_1 \ ,\ m_2 \ ,\ \ …\ \ , \ m_n $ 两两互质

故对于 xx 解的第 ii 项 对 mim_i 取模会得到 ai  (mod  mi)a_i \ \ (mod \ \ m_i)

而其他项中包含的 $M_j \ \ mod \ \ m_j \equiv 0 $

即可以得到对于任意的 ii 都有 $ x \ \equiv \ a_1 \ \ (mod \ \ m_1)$