数学知识

· · 个人记录

斐波那契数

gcd(f_n,f_m) = f_{gcd(n,m)}

1: gcd(f_n,f_m)=gcd(f_n-f_m,f_m) (n>=m)

2: gcd(a*b,c) = gcd(a,c)*gcd(b,c)

3: f_{n+m} = f_n*f_{m+1}+f_{n-1}*f_m

证明：

f_{n+m} = f_{n+m-1}+f_{n+m-2} = 2*f_{n+m-2}+f_{n+m-3} = 3*f_{n+m-3} + 2*f_{n+m-4} = ...... f_{n+m} = f_2*f_{n+m-1}+f_1*f_{n+m-2} = f_3*f_{n+m-2}+f_2*f_{n+m-3} = f_4*f_{n+m-3} + f_3*f_{n+m-4} = ...... = f_n*f_{m+1}+f_{n-1}*f_m

4: gcd(f_m,f_{m+1}) = 1

gcd(f_{n+m},f_m) = gcd(f_n*f_{m+1}+f_{n-1}*f_m,f_m) = gcd(f_n*f_{m+1},f_m) = gcd(f_n,f_m) * gcd(f_{m+1},f_m) = gcd(f_n,f_m) gcd(f_{n+m},f_m) = gcd(f_n,f_m)$ 类似-> $gcd(a,b)=gcd(a-b,b) gcd(f_n,f_m) = f_{gcd(n,m)}

中国剩余定理

若有${\Large \begin{cases} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\... \\x \equiv a_n \pmod{m_n} \end{cases}}

设{\Large M = \sum_{i=1}^{n}m_i }

{\Large M_i=\frac{M}{m_i}, M_i\cdot t_i \equiv 1 \pmod{m_i}}

使得：{\Large x\equiv\sum_{i=1}^{n}a_i\cdot M_i \cdot t_i\pmod{M}}

扩展中国剩余定理

#include<bits/stdc++.h>
using namespace std ;
#define LL long long 
#define Int __int128
int n ;
Int exgcd(Int a , Int b , Int &x , Int &y){
    if(b == 0){
        x = 1 , y = 0 ;
        return a ;
    }
    Int d = exgcd(b , a%b , y , x) ;
    y -= a / b * x ;
    return d ;
}
Int excrt(){ // 扩展中国剩余定理。(将两个同余方程化成一个同余方程) 
    scanf("%d", &n) ; 
    LL x , y ;
    // 这里将形如 x ≡ a mod(m) 化成 x = mk + a , k为任意整数。
    Int k1 , k2 , m1 = 1 , m2 , a1 = 0 , a2 ;
    for(int i = 1 ; i <= n ; i++){
        scanf("%lld%lld", &x , &y) ; // 输出第二个同余方程。
        m2 = (Int)x , a2 = (Int)y ; 
        Int d = exgcd(m1 , m2 , k1 , k2) ; // 用扩展欧几里得算法求线性同余方程的解，并返回m1,m2最大公因数。
        if((a2-a1) % d) return -1 ; // 判断不定方程是否有整数解。
        k1 *= (a2-a1) / d ; // 将不定方程两边乘上（a2-a1）/ d ，变成 m1k1+m2k2=a2-a1。
        k1 = (k1 % (m2/d) + (m2/d)) % (m2/d) ; // 将k1化为不定方程最小正整数解。
        a1 += m1 * k1 ;
        m1 = m1 / d * m2 ; 
    }
    return (a1 % m1 + m1) % m1 ; // 将ans化为不定方程最小正整数解。
}
int main(){
    printf("%lld\n", (LL)excrt()) ;
    return 0 ;
}

二项式定理：

{\Large (a+b)^n=\sum_{k=0}^{n}{}C_{n}^{k}a^{n-k}b^k }

最大公约数

{\Large \left ( a_1,a_2, \dots ,a_n \right ) = \left ( a_1,a_2-a_1, \dots ,a_n-a_{n-1} \right ) }

卢卡斯定理：

设{\Large n = n_1\cdot p + r_1 , m = m_1\cdot p+r_2 }

则{\Large C_{n}^{m} \equiv C_{r_1}^{r_2} \cdot C_{n_1}^{m_1} \pmod{p} --(1)}

证明

O(n)求乘法逆元

#include<bits/stdc++.h>
using namespace std ;
#define LL long long
const int N = 3e6 + 10 ;
int n , p ;
LL ny[N] ;
int main(){
    scanf("%d%d", &n , &p) ;
    for(int i = 1 ; i <= n ; i++){
        ny[i] = (p - p/i) * ny[p%i] % p ;
        if(i == 1) ny[i] = 1 ;
        printf("%lld\n", ny[i]) ;
    }
    return 0 ;
}

欧拉定理

拓展欧拉定理

{\Large \mathrm {a^{b}\equiv a^{b \bmod \varphi (m) + \varphi (m) \ } \pmod{m} }(b \ge \varphi(m)) }