`算法知识` 欧拉定理, 费马小定理

算法 {欧拉函数}
@LOC: 2

欧拉函数

定义

F(x) 其中x为非负整数, 表示[0, x]范围内与x互质的整数个数;
. 比如x=4, 互质的数为{1,3}, 所以F(4)=2;

相關定義

#計算式#
設x的質因子集合為{pi}, 則F(x) == x * [(p1-1)/p1] * [(p2-1)/p2] * ...;
. #證明#: 因為歐拉函數是積性函數 所以F(x) == F(p1^k1) * F(p2^k2) * ..., 所以我們單獨證明F(p^k) == p^k * [(p-1)/p]; 比如設p=5 對於p^k 對[1,p^k]內的所有數 每p個數劃分為一組: (1,2,3,4,5), (6,7,8,9,10), ..., 每個組裡 只有一個1個數是與p^k不互質的(即[5,10,15,...]), 一共是有p^(k-1)個組, 因此與p^k互質的個數 是p^k - p^(k-1), 化簡即可得上述結論;

性质

算法

求一個數的歐拉函數值 ($O(1)$)

{ // 求歐拉函數 ($O(1)$)
    auto ___a = ?;
    ASSERT_( ___a >= 1);
    auto ___EulerFunc = ___a;
    for( auto & [___p, ___k] : `___a的質因數分解`){
        ___EulerFunc /= ___p, ___EulerFunc *= (___p - 1);
    }
    cout<< ___EulerFunc<<"\n";
} // 求歐拉函數 ($O(1)$)
1
2
3
4
5
6
7
8
9

線性篩[1,a]範圍內 所有數的歐拉函數值

定義

在O(N)的時間裡 計算出[1,...,N]每個數的歐拉函數值;

代碼

namespace ___LinearSieve_EulerFunc{
vector Is_prime; // `Is_prime[a]`表示`a`是否為質數;
vector Primes; // [2,3,5,7,...] 表示`[1,...,Range]`裡所有的質數;
vector EulerFunc; // 一個數的歐拉函數值

void Initialize( int _range){ // 处理的數據范围為`[1,...,range]`;
    ASSERT_( _range >= 1);
    Primes.reserve( _range);  Primes.clear();
    Is_prime.assign( _range + 1, true);
    EulerFunc.resize( _range + 1);

    Is_prime[1]=false; EulerFunc[1] = 1;
    for( int num = 2; num <= _range; ++num){
        if( Is_prime[ num]){
            Primes.push_back( num);
            EulerFunc[ num] = num-1;
        }
        for( int ind = 0;; ++ind){
            int tar = Primes[ ind] * num;  if( tar > _range){ break;}
            Is_prime[ tar] = false;
            //>< `num`的最小的質因子 一定是`>= Primes[ind]`;
            if( num % Primes[ ind] == 0){ // 比如`num`的質因子為`{5,11}`, 那麼此時`Primes[ind] == 5`;
                EulerFunc[ tar] = EulerFunc[num] * Primes[ind];
                break;
            }
            //>< 比如`num`的質因子為`{5,11}`, 那麼此時`Primes[ind] == {2/3}`;
            EulerFunc[ tar] = EulerFunc[num] * (Primes[ind] - 1);
        }
    }
}
} // namespace ___LinearSieve_EulerFunc
@TODO( ___LinearSieve_EulerFunc::Initialize( ?));
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

求$N\times N$裡互質的數對的個數

@MARK: @LOC_0;

定義

求([1,N], [1,N])數對裡 互質的數對;
比如N=3, 有(1,1), (1,2), (2,1), (1,3), (3,1), (2,3), (3,2), 即只有(2,2) (3,3)是不互質的 (即GCD != 1);

性質

對於([1,N], [1,N])數對裡 互質的數對(a,b), 我們令m = max(a,b), 令F(x)為m==x的數對個數
@IF(m==1): F(m) == 1, 對應(1,1)這個數對;
@ELSE: F(m) = EulerFunc(m) * 2, 因為歐拉函數就是處理互質的, 比如[1,6]裡面 與6互質的是(1,6), (5,6);

代碼

int64_t ANS = 0;
ANS += 1; // (1,1)
FOR_( i, 2, N){
	ANS += ___LinearSieve_EulerFunc::EulerFunc[ i] * 2; // (?,i)與(i,?)
}
1
2
3
4
5

例題

@LINK: https://editor.csdn.net/md/?articleId=128728184;

求$N\times N$裡 GCD==質數的數對的個數

@MARK: @LOC_1;

詳見@LINK: https://editor.csdn.net/md/?articleId=128728901;

錯誤

#F(x) = x * [(p1-1)/p1] * [(p2-1)/p2] * ... = (p1-1)*(p2-1)*...#
錯誤;
如果x = p1*p2*... 這確實是成立的 即所有指數都為1, 但如果x = p1^(>1) 這就不對了;

筆記

---

## 性质

---

### 欧拉集合的乘积

M下的欧拉集合{m1, m2, …}, 其乘积m1 * m2 * …, 与M互质;

根据: (A,M)互质 (B,M)互质, 则(A*B, M)互质

---

### 欧拉集合乘互质数

对于一个M的欧拉集合S{…} (集合里的每个元素, 与M互质)

则, S集合每个元素mi 同乘 P(其中(P,M)互质), 形成的集合, 在取模M下, 依然等于S

证明:
1, mi * P 与M互质; (因为(mi, M)互质, (P, M)互质; 则(mi * P, M)也互质)
2, mi * P != mj * P (% M), (因为mi != mi, 同乘P (且(P, M)互质), 则mi * P != mj * P, 根据: 取模的乘法

根据这2条性质, (mi * P)的集合, 在%M后, 依然等于S集合;

比如: M = 10, 欧拉集合是:[1, 3, 7, 9]
其 * 3后: [3, 9, 1, 7];
其 * 7后: [7, 1, 9, 3];

但是 * 2后是 [2, 6, 4, 8], 并不等于欧拉集合

---

### 所有互质数
欧拉函数虽然指的是: [0, M)之间, 与M互质的数;
但实际上, 对于任意的(P, M)互质, (P % M)一定在该欧拉集合里;

证明: 令A = P % M, A在[0, M)里; P = A + k * M
假如(A, M)不互质, 存在g | A, g | M, 那么, P = k1 * g, 与(P, M)互质矛盾

比如M = 10, 欧拉集合是{1, 3, 7, 9}, 这些数均与M互质;
那么, 所有与M互质的数, 一定是形如: {1 或 3 或 7 或 9} + k * M

---

## 例子

一些积性函数的例子:

欧拉函数

约数函数: F( x)表示x这个数的约数个数, 他等于: (a1 + 1) * (a2 + 1) * ... (ai为各个质因子的量级)
令Pow( x)为: x的最小的质因子的量级.
则, 约数函数可以用 在(线性筛质数)时, 线性的构造出来

if( i % Prime[ j] == 0){
	F[ Prime[ j] * i] = F[ i] / Pow[ i] * ( Pow[ i] + 1);
}
else{
	F[ Prime[ j] * i] = F[ i] * 2;
}
1
2
3
4
5
6

约数之和函数: F( x)表示x这个数的 所有约数之和, 他等于: $(1+p_1+p_1^2+...)\ast (1+p_2+p_2^2+...)...$
令Min( x)为: $x的(1+p_1+p_1^2+...),p_1为x的最小质因子$
你可以研究下, 他也可以配合(线性筛质数)时, 线性的构造出来

---

## 性质

(1, 欧拉函数 是 积性函数.
$\varphi (12)=4,\varphi (2)=1,\varphi (6)=2,\varphi (3)=2,\varphi (4)=2$
… 因为3, 4互质, 但是2, 6不是互质的;
… 所以, $\varphi (3)\ast \varphi (4)=4=\varphi (12)$, 但是, 从$\varphi (2)\ast \varphi (6)$并不能推出$\varphi (12)$, 因为2, 6两者不互质.

证明: 简单证明, 如果你知道欧拉函数的公式的话
… 对于任意一个数, 其欧拉函数公式为: $\varphi (p_1^{k_1}\ast p_2^{k_2}\ast p_3^{k_3}...)=(p_1^{k_1}\ast p_2^{k_2}\ast p_3^{k_3}...)\ast \frac{p_1-1}{p_1}\ast \frac{p_2-1}{p_2}\ast \frac{p_3-1}{p_3}\ast ...$
… 合并同类项后, : $(p_1^{k_1}\ast \frac{p_1-1}{p_1})\ast (p_2^{k_2}\ast \frac{p_2-1}{p_2})\ast (p_3^{k_3}\ast \frac{p_3-1}{p_3})...=\varphi (p_1^{k_1})\ast \varphi (p_2^{k_2})\ast \varphi (p_3^{k_3})...$
… 即: $\varphi (p_1^{k_1}\ast p_2^{k_2}\ast p_3^{k_3}...)=\varphi (p_1^{k_1})\ast \varphi (p_2^{k_2})\ast \varphi (p_3^{k_3})...$
… 而, $p_1^{k_1},p_2^{k_2},p_3^{k_3}$这些项, 是互相互质的; 即: $\varphi (n)$, 可以拆分成这些项的乘积
… 对于任意的 a ∗ b = n , 且 a , b 互质 (这是积性函数的前提), 则此时, a一定是上面公式中某些项的乘积, b是剩余项的乘积
… 因此, 满足: $f(a\ast b)=f(a)\ast f(b)$

$令C(x)为:\forall i\in [1,N],且满足:gcd(i,N)=x条件的,i的个数$
(注意, C(x)不是表示gcd( x, N), 这里脑子要转转)

---

… 结论三: $C(i)=\varphi (N/i)$ (对于C(i) != 0来说)

---

比如举个例子: N = 12,
我们拿12个数[1, 2, .., 12], 根据他们和12的gcd, 进行分离
当x为{1, 5, 7, 11}时, 此时GCD( x, 12) = g = 1, 他的个数 等于12 / g = 12的欧拉函数
当x为{2, 10}时, 此时GCD( x, 12) = g = 2, 他的个数 等于12 / g = 6的欧拉函数
当x为{3, 9}时, 此时GCD( x, 12) = g = 3, 他的个数 等于12 / g = 4的欧拉函数
当x为{4, 8}时, 此时GCD( x, 12) = g = 4, 他的个数 等于12 / g = 3的欧拉函数
当x为{6}时, 此时GCD( x, 12) = g = 6, 他的个数 等于12 / g = 2的欧拉函数
当x为{12}时, 此时GCD( x, 12) = g = 12, 他的个数 等于12 / g = 1的欧拉函数

… 对于某一类, 比如GCD( {3/9, 12}) = 3来说, 即gcd( x, N) = g, 让x, N都/= g(可以整除的)
… 变成: gcd( {1,3}, 4) = 1, 而这个式子, 就是N/g = 4的欧拉函数

---

---

## 证明
令N为M的欧拉函数值, 其欧拉集合S1: {m1, m2, …, mN}
将S1中每个元素 * P, 其中(P, M)互质, 得到集合S2: {m1 * P, m2 * P, …, mN * P}

根据: 欧拉集合 * 互质数, 可知, S2集合 在%M意义下, 等于S1
比如: M = 10, 欧拉集合S1是{1, 3, 7, 9}
令P = 3, S2集合为{3, 9, 21, 27}, S2集合在%M下为{3, 9, 1, 7} 等于S1集合

S1所有元素的乘积记作Mul1 = (m1 * m2 * … * mN)
S2所有元素的乘积记作Mul2 = (m1 * P * m2 * P * … * mN * P)
则: Mul1 = Mul2 (% M); (因为, S2集合在%M下 等于 S1集合;)

即: Mul1 = Mul2 = Mul1 * P^N (% M)

因为, 根据: 欧拉函数的乘积, 得到(Mul1, M)互质

根据取模的除法, 此时: Mul1 = Mul1 * P^N ( % M), 可以把Mul1去掉

即 1 = P^N (% M)

---

欧拉定理的思路是: 一个欧拉集合S1 (其每个元素均与M互质), 构造一个新的集合S2 (由S1 * P得到, (P, M)互质)

假如, S1不是欧拉集合, 而是取模集合 [1, 2, 3, …, M - 1], 可以吗?
虽然此时也会有: S2集合 在取模意义下, 等于S1集合; 即: Mul1 = Mul2 = Mul1 * P^N
但是, 此时Mul1与M不互质, 因此, 不能把Mul1给约去掉; 从而得到1 = P^N

假如, P不是质数, 可以吗?
如果P不是质数, 则S2集合 在取模意义下, 不等于S1
因此, Mul1 = Mul2 不成立;