数论基础

男娘i 2022-02-04 09:11 345阅读 0赞

# 数论 #

## 质数筛选 ##

### 素数筛 ###

//复杂度（NlogN）
    for (int i = 2; i <= n; ++i) {
        is_prime[i] = 1;
    }
    for (int i = 2; i * i <= n; ++i) {
        if (is_prime[i]) {
            for (int j = i * i; j <= n; j +=i) {
                 is_prime[j] = 0;
            }
        }
    }

## 欧拉函数与积性函数 ##

### 概述 ###

\*\*欧拉函数：\*\*对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目（φ(1)=1）。

**通式：**

![img][]

其中p1, p2……pn为x的所有质因数，x是不为0的整数。

φ(1)=1（和1[互质][Link 1]的数(小于等于1)就是1本身）。

**积性函数：对于任意互质的整数**a和b有性质f(ab)=f(a)f(b)的数论函数。

欧拉函数φ(n)为积性函数，但是不是完全积性函数

Φ \\Phi Φ § = p-1

Φ \\Phi Φ ( p k p^k pk) =  p k p^k pk \-  p k − 1 p^ \{k-1\} pk−1 =  ( p − 1 ) p k − 1 (p-1)p^\{k-1\} (p−1)pk−1

若m,n互质，则有  Φ \\Phi Φ (mn) =  Φ \\Phi Φ (m)  Φ \\Phi Φ(n).

**完全积性函数：对于任意整数**a和b有性质f(ab)=f(a)f(b)的数论函数。

--------------------

### 欧拉定理 ###

若a, n互质， 则有

$ a^\{φ(n)\} \\equiv 1 (mod n) $

\*\*特例：\*\*费马小定理

a p − 1 ≡ 1 ( m o d p ) a^\{p-1\} \\equiv 1(mod p) ap−1≡1(modp) , 其中p为质数。

**其他性质：**

∑ d ∣ n Φ ( d ) = n \\sum\_\{d|n\} \\Phi(d) = n ∑d∣nΦ(d)=n

**原根**

原根，是一个数学符号。设m是正整数，a是整数，若a模m的阶等于φ(m)，则称a为模m的一个原根。

当模p有原根时，它有φ(φ(m))个原根。

--------------------

## 扩展欧几里得 ##

int exgcd (int a, int b, int &x, int &y){
        if(b==0){
            x = 1;
            y = 0;
            return a;
        }
        int r = exgcd(b, a%b, x, y);
        int t = x; 
        x = y;
        y = t-a/b*y;
        return r;
    }

d = g c d ( a , b ) ; d = gcd(a, b); d=gcd(a,b);

通过扩展欧几里得得出方程的一组特解，假设特解为( x 0 , y 0 x\_0, y\_0 x0,y0), 满足 a x 0 + b y 0 = d ax\_0 + by\_0 = d ax0\+by0=d, 那么有

a ( x 0 + k b d ) + b ( y 0 − k a d ) = d , 其 中 k ∈ Z a(x\_0 + k\\frac \{b\}\{d\}) + b(y\_0 - k\\frac\{a\}\{d\}) = d, 其中k\\in Z a(x0\+kdb)\+b(y0−kda)=d,其中k∈Z

则**方程的通解**为

x = x 0 + k b d x = x\_0 + k\\frac\{b\}\{d\} x=x0\+kdb

y = y 0 + k a d y = y\_0 + k\\frac\{a\}\{d\} y=y0\+kda

### 乘法逆元 ###

a x ≡ 1 ( m o d p ) ax\\equiv 1(mod p) ax≡1(modp)

扩展gcd求逆元

a关于p的逆元存在充要条件a, p互质

然后将除法取模转化为乘法取模

如果p为质数，则可根据费马小定理得出

x\*a%p =  a p − 1 a^\{p-1\} ap−1%p=1

用二分快速幂加速求解

**线性预处理逆元：**

对于一段区间上的逆元，在线性时间上预处理出来

i n v i = ( p − p i ) i n v p % i % p inv\_i=(p-\\frac\{p\}\{i\})inv \_\{p\\%i\} \\%p invi=(p−ip)invp%i%p

//p必须为质数， p/i为整除
    inv[1] = 1;
    for (int i=2; i<=n; ++i){
    	inv[i] = (p-p/i) * inv[p%i] % p;
    }

**证明：**

i ⋅ i n v i % p = i ∗ ( p − p i ) i n v p % i % p = i ∗ ( p − p − p % i i ) i n v p % i % p = p % i ∗ i n v p % i % p = 1 \{i\\cdot inv\_i\}\\%p = i \* (p-\\frac\{p\}\{i\})inv \_\{p\\%i\}\\%p = i\*(p-\\frac\{p-p\\%i\}\{i\})inv \_\{p\\%i\}\\%p = p\\%i\*inv \_\{p\\%i\}\\%p = 1 i⋅invi%p=i∗(p−ip)invp%i%p=i∗(p−ip−p%i)invp%i%p=p%i∗invp%i%p=1

**应用：**

**求组合数学取模:**

f a c t i = 1 ∗ 2 ∗ 3 ⋯ i % p , i n v s i = i n v 1 ∗ i n v 2 ⋯ i n v i % p fact\_i = 1\*2\*3\\cdots i\\%p, \\qquad invs\_i = inv\_1 \* inv\_2 \\cdots inv\_i\\%p facti=1∗2∗3⋯i%p,invsi=inv1∗inv2⋯invi%p

C n m % p = n ! m ! ( n − m ) ! % p = f a c t n ∗ i n v s m ∗ i n v s n − m % p C\{^m\_n\}\\%p = \\frac\{n!\}\{m!(n-m)!\}\\%p = fact\_n \* invs\_m \* invs\_\{n-m\}\\%p Cnm%p=m!(n−m)!n!%p=factn∗invsm∗invsn−m%p

## 中国剩余定理（模线性方程组） ##

**一元模线性方程组：**

x ≡ a 1 ( m o d &ThinSpace;&ThinSpace; m 1 ) x \\equiv a\_1 (\\mod m\_1) x≡a1(modm1)

x ≡ a 2 ( m o d &ThinSpace;&ThinSpace; m 2 ) x \\equiv a\_2 (\\mod m\_2) x≡a2(modm2)

⋯ \\cdots ⋯

x ≡ a n ( m o d &ThinSpace;&ThinSpace; m n ) x \\equiv a\_n (\\mod m\_n) x≡an(modmn)

**剩余定理：**

假设整数 m 1 , m 2 , ⋯ &ThinSpace; , m n m\_1, m\_2, \\cdots, m\_n m1,m2,⋯,mn两两互质，则方程组有解，通解可以构造如下：

设M =  m 1 × m 2 × ⋯ × m n = ∏ m i m\_1 \\times m\_2 \\times \\cdots \\times m\_n = \\prod m\_i m1×m2×⋯×mn=∏mi, 并设  M i = M / m i , t i = M i − 1 M\_i = M/m\_i, t\_i = M\_i^\{-1\} Mi=M/mi,ti=Mi−1, 表示 M i 模 m i 意 义 下 的 倒 数 ， 即 M i t i ≡ 1 % m i M\_i 模m\_i意义下的倒数，即M\_it\_i\\equiv 1\\%m\_i Mi模mi意义下的倒数，即Miti≡1%mi

**方程式的通解**

x = a 1 t 1 M 1 + a 2 t 2 M 2 + ⋯ + a n t n M n + k M = ∑ i = 1 n a i t i M i + k M x = a\_1t\_1M\_1 + a\_2t\_2M\_2 + \\cdots + a\_nt\_nM\_n + kM = \\sum\_\{i=1\}^\{n\} a\_it\_iM\_i +kM x=a1t1M1\+a2t2M2\+⋯\+antnMn\+kM=i=1∑naitiMi\+kM

**各m互质：**

ll CRT (ll a[], ll m[], ll n){
        ll M = 1;
        ll ans = 0;
        for (int i=1; i<=n; i++){
            M *= m[i];
        }
        for (int i=1; i<=n; i++){
            ll x, y;
            ll Mi = M/m[i];
            exgcd(Mi, m[i], x, y);
            ans = (ans + Mi*x*a[i])%M;
        }
        if(ans<0) ans += M;
        return ans;
    }

**各m不互质：**

对模线性方程两两合并

**推导**：  x ≡ a 1 ( m o d &ThinSpace;&ThinSpace; m 1 ) x \\equiv a\_1 (\\mod m\_1) x≡a1(modm1)

x ≡ a 2 ( m o d &ThinSpace;&ThinSpace; m 2 ) x \\equiv a\_2 (\\mod m\_2) x≡a2(modm2)

对于两个模线性方程则有

x = m 1 k 1 + a 1 = m 2 k 2 + a 2 x = m\_1k\_1+a\_1 = m\_2k\_2+a\_2 x=m1k1\+a1=m2k2\+a2

得到  m 1 k 1 + m 2 ( − k 2 ) = a 2 − a 1 m\_1k\_1 + m\_2(-k\_2) = a\_2-a\_1 m1k1\+m2(−k2)=a2−a1

通过扩展欧几里得可得到该方程的最小正整数解k是方程 x = m 1 k 1 + a 1 x = m\_1k\_1+a\_1 x=m1k1\+a1成立, x为两个方程的最小正整数解

可得出两个方程的通解为：

X = x + k ∗ L C M ( m 1 , m 2 ) X = x + k\*LCM(m\_1,m\_2) X=x\+k∗LCM(m1,m2)

从而得到最终的合并方程

X = x ( m o d &ThinSpace;&ThinSpace; L c m ( m 1 , m 2 ) ) X = x(\\mod Lcm(m\_1, m\_2)) X=x(modLcm(m1,m2))

ll exCRT (ll a[], ll m[], ll n){
        ll M=m[1], A=a[1], t, d, x, y;
        for (int i=2; i<=n; i++){
            d = exgcd(M,m[i],x, y);
            if((a[i]-A)%d){
                return -1;
            }
            x *= (a[i]-A)/d;
            t = m[i]/d;
            x=(x%t+t)%t;
            A = M*x+A, M=M/d*m[i], A%=M;
        }
        A=(A%M+M)%M;
        return A;
    }

## 二分快速幂 ##

**思想：**

如果b是偶数，则有 a b = ( a b 2 ) 2 a^b = (a^\{\\frac\{b\}\{2\}\})^2 ab=(a2b)2

如果b是奇数，则有 a b = ( a b − 1 2 ) 2 ∗ a a^b = (a^\{\\frac\{b-1\}\{2\}\})^2\*a ab=(a2b−1)2∗a

**代码实现：**

//递归形式
    int Pow_mod (int a, int b, int mod){
        if(b==0){
            return 1%mod;
        }
        int temp = pow(a, b/2, mod);
        temp = temp*temp%mod;
        if(b&1){
            temp = temp*a%mod;
        }
        return temp;
    }
    //循环形式
    int pow_mod (int a, int b, int mod){
        int res = 1, temp = a;
        while(b){
            if(b&1){
                res = res*temp%mod;
            }
            temp = temp*temp%mod;
            b /= 2;
        }
        return res;
    }

## 矩阵快速幂 ##

**推出递推式，并用矩阵乘法表示**

\*\*eg:\*\*斐波那契数列的递推式推导

A = \[ 1 1 1 0 \] A = \\begin \{bmatrix\} 1&1 \\\\ 1& 0\\end\{bmatrix\} A=\[1110\]

\[ f \[ i \] f \[ i − 1 \] \] = A i − 2 ⋅ \[ f \[ 2 \] f \[ 1 \] \] \\begin \{bmatrix\} f\[i\]\\\\ f\[i-1\]\\end \{bmatrix\} = A^\{i-2\} \\cdot \\begin \{bmatrix\} f\[2\]\\\\ f\[1\]\\end \{bmatrix\} \[f\[i\]f\[i−1\]\]=Ai−2⋅\[f\[2\]f\[1\]\]

//求10^18以内的斐波那契数,并对m取模
    package com.mine.math;
    
    import java.util.Scanner;
    
    class matrix {
        
    	int n;
    	int m;
    	long[][] a;
    	public matrix() {
        
    	}
    	public matrix(int n, int m) {
        
    		this.n = n;
    		this.m = m;
    		this.a = new long[n][m];
    	}
    }
    public class _37732 {
        
    	public static void main(String[] args) {
        
    		Scanner input = new Scanner(System.in);
    		long n = input.nextLong();
    		long m = input.nextLong();
    		if(n<3) {
        
    			System.out.println(1%m);
    		} else {
        
    			matrix A = new matrix(2,2);
    			A.a[0][0] = 1;
    			A.a[1][0] = 1;
    			A.a[0][1] = 1;
    			matrix res = matrix_pow(A, n-2, m);
    			System.out.println(res.a[0][0]);
    		}
    		input.close();
    	}
    
    	private static matrix matrix_pow(matrix A, long n, long mod) {
        
    		matrix res = unit(), temp = A;
    		while(n!=0) {
        
    			if((n&1)==1) {
        
    				res = matrix_mul(temp, res, mod);
    			}
    			temp = matrix_mul(temp, temp, mod);
    			n /= 2;
    		}
    		return res;
    	}
    
    	private static matrix matrix_mul(matrix A, matrix B, long mod) {
        
    		matrix C = new matrix(2, 2);
    		for (int i=0; i<A.n; ++i) {
        
    			for (int j=0; j<B.m; ++j) {
        
    				C.a[i][j] = 0;
    				for (int k=0; k<A.m; ++k) {
        
    					C.a[i][j] += A.a[i][k]*B.a[k][j]%mod;
    					C.a[i][j] %= mod;
    				}
    			}
    		}
    		return C;
    	}
    	private static matrix unit() {
        
    		matrix C = new matrix(2,1);
    		C.a[0][0] = 1;
    		C.a[1][0] = 1;
    		return C;
    	}
    }

[img]: https://gss0.bdstatic.com/-4o3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D146/sign=972114bf49a98226bcc12f23bc80b97a/f3d3572c11dfa9ecf6f6c0dd68d0f703908fc124.jpg
[Link 1]: https://baike.baidu.com/item/%E4%BA%92%E8%B4%A8