数论

质数筛选

素数筛

//复杂度（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）。

​ 通式：

​

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

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

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

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

​ $\Phi$ § = p-1

​ $\Phi$ ($p^k$) = $p^k$ - $p^{k-1}$ = $(p-1)p^{k-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}\equiv 1(modp)$ , 其中p为质数。

其他性质：

${\sum }_{d|n}\Phi (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=gcd(a,b);$$

通过扩展欧几里得得出方程的一组特解，假设特解为($x_0,y_0$), 满足$$a{x}_0+b{y}_0=d$$, 那么有

​ $$a(x_0+k\frac{b}{d})+b(y_0-k\frac{a}{d})=d,其中k\in Z$$

则方程的通解为

​ $$x=x_0+k\frac{b}{d}$$

​ $$y=y_0+k\frac{a}{d}$$

乘法逆元

$ax\equiv 1(modp)$

扩展gcd求逆元

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

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

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

x*a%p = $a^{p-1}$%p=1

用二分快速幂加速求解

线性预处理逆元：

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

$$in{v}_i=(p-\frac{p}{i})in{v}_{p\%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\cdot in{v}_i\%p=i\ast (p-\frac{p}{i})in{v}_{p\%i}\%p=i\ast (p-\frac{p-p\%i}{i})in{v}_{p\%i}\%p=p\%i\ast in{v}_{p\%i}\%p=1$$

应用：

求组合数学取模:

​ $fac{t}_i=1\ast 2\ast 3\cdots i\%p,inv{s}_i=in{v}_1\ast in{v}_2\cdots in{v}_i\%p$

​ $C{}_n^m\%p=\frac{n!}{m!(n-m)!}\%p=fac{t}_n\ast inv{s}_m\ast inv{s}_{n-m}\%p$

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

一元模线性方程组：

​ $$x\equiv a_1(\mathrm{m}\mathrm{o}\mathrm{d}{m}_1)$$

​ $$x\equiv a_2(\mathrm{m}\mathrm{o}\mathrm{d}{m}_2)$$

​ $$\cdots$$

​ $$x\equiv a_n(\mathrm{m}\mathrm{o}\mathrm{d}{m}_n)$$

剩余定理：

​ 假设整数$m_1,m_2,\cdots ,m_n$两两互质，则方程组有解，通解可以构造如下：

​ 设M = $m_1\times m_2\times \cdots \times m_n=\prod m_i$, 并设 $M_i=M/m_i,t_i=M_i^{-1}$, 表示$M_i模m_i意义下的倒数，即M_i{t}_i\equiv 1\%m_i$

​ 方程式的通解

​ $$x=a_1{t}_1{M}_1+a_2{t}_2{M}_2+\cdots +a_n{t}_n{M}_n+kM=\sum _{i=1}^n{a}_i{t}_i{M}_i+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\equiv a_1(\mathrm{m}\mathrm{o}\mathrm{d}{m}_1)$$

​ $$x\equiv a_2(\mathrm{m}\mathrm{o}\mathrm{d}{m}_2)$$

​ 对于两个模线性方程则有

​ $$x=m_1{k}_1+a_1=m_2{k}_2+a_2$$

​ 得到 $$m_1{k}_1+m_2(-k_2)=a_2-a_1$$

​ 通过扩展欧几里得可得到该方程的最小正整数解k是方程$$x=m_1{k}_1+a_1$$成立, x为两个方程的最小正整数解

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

​ $$X=x+k\ast LCM(m_1,m_2)$$

​ 从而得到最终的合并方程

​ $$X=x(\mathrm{m}\mathrm{o}\mathrm{d}Lcm(m_1,m_2))$$

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^{\frac{b}{2}}{)}^2$$

​ 如果b是奇数，则有$$a^b=(a^{\frac{b-1}{2}}{)}^2\ast 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=\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]$$

$$\left[\begin{array}{c}f[i]\\ f[i-1]\end{array}\right]=A^{i-2}\cdot \left[\begin{array}{c}f[2]\\ f[1]\end{array}\right]$$

//求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;
	}
}