基础数论

基础数论

整除

一、概念

若整数a除以非零整数b，商为整数，且余数为零，我们就说b能整除a，即b|a，读作"b整除a"或"a除以b"。
可以理解为b是a的因子，a是b的倍数。

二、性质

(1.传递性：如果a:|:b且b:|:c，那么a:|:c)

(2.结合性：a:|:b且a:|:c，那么对于任意整数x和y，有a:|:(b*x+c*y))

(3.同除性：设m:!= 0，那么a:|:b等价于(m*a):|:(m*b))

(4.条件性: a = q*b + r:， b:|: a等价于 r:|:b)

(5.a:|:c:,: b:|:c:,: gcd(a,b)=1 那么 ab:|:c)

(6.p:|:ab , 那么p:|:a或p:|:b , 如果gcd(p,a) = 1 , 那么p:|:b)

同余

一、概念

(给定一个正整数m，如果两个整数a和b满足a-b能够被m整除，即m|(a-b)，那么就称整数a与b对模m同余。)
(记作a≡b(mod:m)。对模m同余是整数的一个等价关系。可表示为a≡b(mod:m)⇐⇒m|(a−b))

二、性质

(1.可加减性:aequiv b(mod:m) , cequiv d(mod:m) ightarrow a+cequiv b+d(mod:m))
(证明:可知有:m:|:a-b , m:|:c-d , 根据整除结合性有m:|:a+c-b-d , 得证 a+cequiv b+d(mod:m))

(2.可乘性:aequiv b(mod:m) , c equiv d (mod:m) ightarrow ac equiv bd(mod:m))
(证明:可知有：a = q_1m+b , c = q_2m+d ightarrow ac = (q_1q_2m+q_1d+q_2b)m + cd 。根据同余得证 ightarrow acequiv bd(mod:m))

(3.注意除法不具有一般消去律:gcd(c , m) = d , ac equiv bc(mod:m) ightarrow a equiv b (mod:frac{m}{d}))
(证明：已知有m:|:c(a-b)。 两边同时除d , frac{m}{d} :|: frac{c}{d} (a-b) , 可知gcd(frac{c}{d} , frac{m}{d}) = 1 , 根据上整除性质5可得, frac{m}{d} | (a - b) , 得证 a equiv b (mod:frac{m}{d}))

模运算与取余

一、概念

取模运算（“Modulus Operation”）和取余运算（“Remainder Operation ”）两个概念有重叠的部分但又不完全一致。
主要的区别在于对负整数进行除法运算时操作不同。取模主要是用于计算机术语中。取余则更多是数学概念。 ---百度百科

二、区别及运算

(0<=a : mod : m <= m:,:-m<=a \% b<=m ， 所以在求余时，模为负数要转为正数，方法：(a\%m+m)\%m)
计算机上有几种对于结果取整的方法:
1.向上取整：向+∞方向取最接近精确值的整数，也就是取比实际结果稍大的最小整数，也叫 Ceiling 取整。
2.向-∞方向取最接近精确值的整数，也就是取比实际结果稍小的最大整数，也叫 Floor 取整。
3.向零取整，向0方向取最接近精确值的整数，换言之就是舍去小数部分，因此又称截断取整（Truncate）。
cjava：对于模运算采用向零取整。（a % b = a - (a/b)*b）
-17 % 10 的计算结果如下：r = (-17) - (-17 / 10) x 10 = (-17) - (-1 x 10) = -7
17 % -10 的计算结果如下：r = 17 - (17 / -10) x (-10) = (17) - (-1 x -10) = 7
-17 % -10 的计算结果如下：r = (-17) - (-17 / -10) x (-10) = (-17) - (1 x -10) = -7

欧几里得

一、gcd与lcm概念

最大公约数：指两个或多个整数共有约数中最大的一个。(a，b的最大公约数记为gcd（a,b)).
最小公倍数：两个或多个整数公有的倍数叫做它们的公倍数，其中除0以外最小的一个公倍数就叫做这几个整数的最小公倍数。(a,b的最大公倍数记作lcm(a,b)).

二、gcd与lcm性质

(1.gcd(a,b) = gcd(b,a))
(2.gcd(a,b) = gcd(a-b,b)(a>=b)(证明：假设公约数为d , d:|:a , d:|:b , 根据整除性质的结合性 ightarrow d:|:(a-b) , d:|:b))
(3.gcd(a,b) = gcd(a\% b , b)(证明：假设a :，b的gcd(a,b) = d :,: d:|:a :,: d:|:b :,: a = d*q+r : ightarrow : d:|:r . 得证gcd(a,b) = gcd(r,b) = gcd(a\%b , b)))
(4.lcm(a,b) = frac{a*b}{gcd(a,b)}(a*b必为在a,b的倍数,除去最大共因子即为最小公倍数))

三、从唯一分解定理看gcd(a,b)、lcm(a,b)和a*b间的关系

由唯一分解定理：

[a = p^{e_1}_{1} * p^{e_2}_{2} * p^{e_3}_{3} * ... * p^{e_n}_{n} ]

[b = p^{f_1}_{1} * p^{f_2}_{2} * p^{f_3}_{3} * ... * p^{f_n}_{n} ]

[gcd(a,b) = Pi^{n}_{i=1}p^{min(e_i , f_i)}_{i} ]

[lcm(a,b) = Pi^{n}_{i=1}p^{max(e_i , f_i)}_{i} ]

[a * b = Pi^{n}_{i=1} p_i^{min(e_i,f_i)+max(e_i ,f_i)} ]

三、欧几里得求gcd

(已知：gcd(a , b) = gcd(a\%b , b) = gcd(b , a\%b))
(将b看作新的a即a'，a\%b看作b',重复以上两步。直到gcd(a'' , 0) = a''结束.)

int gcd(int a , int b){
    if(b == 0){
        return a ;
    }else{
        gcd(b , a%b);
    }
    //return b==0?a:gcd(b,a%b);
}

扩展欧几里得

一、简介

(解二元一次不定方程a*x+b*y=gcd(a,b).求一组解(x_0,y_0))

[a*x_1 + b*y_1 = gcd(a,b) ]

[b*x_2 + (a\%b)*y_2 = gcd(b , a\%b) ]

由欧几里得可知上面两式相等.

[a*x_1 + b*y_1 = b*x_2 + (a-[frac{a}{b}]*b)*y_2 ]

对等号右边进行合并同类项得

[a*x_1 + b*y_1 = a*y_2 + b*(x_2-[frac{a}{b}]*y_2) ]

得到递推式：

[x_1 = y_2 ]

[y1 = x_2 - frac{a}{b} * y_2 ]

(终止条件：当b = 0 时，有 x_2 = 1 , y_2 = 0.根据递推式反推x_0,y_0.)
代码实现：(可以知道求x_0 , y_0过程是一个递归过程,需要先求得x_2,y_2再根据递推式倒推。)

void ex_gcd(int a , int b , int &d , int &x , int &y){
    if(!b){//终止条件b=0
        d = a ;
        x = 1 ;
        y = 0 ;
    }else{
        ex_gcd(b , a%b , d , x , y);//递归
        //倒推过程
        int t = x ;
        x = y ;
        y = t - (a/b)*y;
    }
}

int cal(int a , int b , int c){
    ex_gcd(a , b , d , x , y);
    int t = b/d;
    return (x%t+t)%t;//得到x得最小正整数解
}

可以知道二元一次方程具有多组解：

[x = x_0 + frac{b}{d}*k (kin Z) ]

[y = y_0 + frac{a}{d}*k (kin Z) ]

一般解题都是要求最小正整数解:(x = (x\%frac{b}{d}+frac{b}{d})\%frac{b}{d})，将x代入方程求出y

二、解二元一次不定方程ax+by=c

有解条件(gcd(a,b)|c).

[x = x*frac{c}{gcd(a,b)} + frac{b}{d}*k ]

[y = y*frac{c}{gcd(a,b)} + frac{a}{d}*k ]

逆元

一.概念

逆元素是指一个可以取消另一给定元素运算的元素，在数学里，逆元素广义化了加法中的加法逆元和乘法中的倒数。---百度百科

在数论同余方程中，对于(a * x≡b（mod:m）)这个方程如果我们要求解的话其实是比较复杂的，可是如果我们可以求出(a * y≡1（mod:m）)中的y的话，
在上面那个方程上同乘以y就可以得到，(x=b * y(mod:m))，是不是很神奇，我们也称y是a在mod m的条件下的逆元，写作(x^{-1})。

二.费马小定理求逆元

费马小定理(Fermat's little theorem)是数论中的一个重要定理，在1636年提出。如果p是一个质数，而整数a不是p的倍数，则有a^（p-1）≡1（mod p） ---百度百科

将费马小定理等式两边同除a（即乘以(a^{-1})) ， 得(a^{-1} equiv a^{p-2}(mod p)) , 所以a的逆元就等于a在模p下得p-2次方，快速幂求解。
注意：费马小定理的两个条件：(gcd(a,p)=1、p为质数)

int quickpow(int a , int b , int mod){
    int ans = 1 ;
    while(b){
        if(b&1){
            ans = ans * a % mod ;
        }
        b >>= 1 ;
        a = a * a % mod ;
    }
    return ans ;
}

int inv(int a , int m){//a在模m下的逆元
    return quickpow(a , m-2 , m);
}

三、扩展欧几里得求逆元

费马小定理求逆元代码很简洁，但有时候求逆元模数p可能不是质数，但有(gcd(a,p) = 1)，存在逆元。
这时候扩展欧几里得得排上用场了。
(a*x equiv 1 (mod:p))，可以转化成二元一次不等式，(a*x+p*k = 1),这时求出x的最小正整数解(x_0)即为a在模p下得逆元。

void ex_gcd(int a , int b , int &d , int &x , int &y){
    if(!b){
        d = a ;
        x = 1 ;
        y = 0 ;
    }else{
        ex_gcd(b , a%b , d , x , y);
        int t = x ;
        x = y ;
        y = t - (a/b)*y;
    }
}

int inv(int a , int p , int c){
    ex_gcd(a , p , d , x , y);
    if(gcd(a,p) != 1) return 0;//不存在逆元
    int t = b/d;
    return (x%t+t)%t;//x得最小正整数解
}

四、线性筛逆元

首先有(1^{-1} equiv 1(mod p))
设(p = k * i + r(k是frac{p}{i}得商 , r是余数))有

[k*i+r equiv 0(mod p) ]

两边乘以(i^{-1} , r^{-1})，得

[k * r^{-1} + i^{-1} equiv 0 (mod p) ]

移项得

[i^{-1} equiv -k*r^{-1} (mod p) ]

将k和r带入得

[i^{-1} equiv -[frac{p}{i}]*(p\%i)^{-1}(mod p) ]

所以有递推式

[inv[i] = (p - [frac{p}{i}]) * inv[p\%i] \% p ]

void solve(){
    inv[1] = 1 ;
    for(int i = 2 ; i < p ; i++){
        inv[i] = (p - p/i) * inv[p%i] % p ;
    }
}

五、阶乘逆元

阶乘逆元(inv[i+1] = frac{1}{(i+1)!})有递推关系：(inv[i] = inv[i+1] * (i+1))
阶乘逆元一般会在求组合数且结果需要mod时出现,先求出1-n的阶乘，再利用扩展欧几里得或则费马小定理求出n阶乘的逆元，根据递推关系倒退1-n-1阶乘得逆元

inv[N]=quickpow(fac[N],mod-2);
for(ll i=N-1;i>=0;i--)
    inv[i]=(inv[i+1]*(i+1))%mod;

中国剩余定理

一、介绍

中国剩余定理是求解一元线性同余方程组

[ left{ egin{aligned} x equiv a_1(mod:m_1)\ x equiv a_2(mod:m_2)\ ................\ x equiv a_n(mod:m_n) end{aligned} ight.]

(m_1 , m_2 , ... , m_n)两两互质，则对任意整数(a_1,a_2,...,a_n)，求最小非负整数解x。

二、求解

令(M = Pi^{n}_{i=1}m_i),M为所有模数得最小公倍数。
令(t_i 为同余方程frac{M}{m}*t_i equiv 1(mod:m_i))的最小非负整数解
则有一个解为 (x = Sigma^{n}_{i=1}a_i*frac{M}{m_i}*t_i)
同解为(x = x + M*q)
最小非负整数解((x\%M+M)\%M.)

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

int CTM(){
    int M = 1 , ans = 0 ;
    rep(i , 1 , n){
        M *= m[i];
    }
    rep(i , 1 , n){
        int t = M/m[i];
        d = ex_gcd(t , m[i] , x , y);
        x = (x % (m[i]/d) + (m[i]/d)) % (m[i]/d) ;//求得x得最小正整数解
        ans = (ans + a[i]*t*x)%M;//求和
    }
    return ans ;
}

三、解扩展中国剩余定理

同样是解一元线性同余方程组，只是不满足(m_1 , m_2 , ... , m_n)两两互质。
解法思想是两两方程合并。
现在演示合并前两个同余方程

[x equiv a_1(mod:m_1) ]

[x equiv a_2(mod:m_2) ]

转为线性方程有

[x + m_1*u = a_1(u为任意整数) ]

[x - m_2*v = a_2(v为任意整数) ]

1式减2式得

[m_1*u + m_2*v = a_1 - a_2 ]

有解条件为(gcd(m_1, m_2)|a_i - a_2)
通过扩展欧几里得可以得到一组解((u_0 , v_0))
有通解(u = u_0 + frac{m_2}{gcd(m1,m2)}*k)（k为任意整数）
带入1式得

[x + lcm(m_1 , m_2)*k = a_1 - m_1*u_0 ]

有合并后同余方程

[x equiv a_1 - m_1*u_0(mod:lcm(m_1 , m_2)) ]

int ex_gcd(int a , int b , int &x , int &y){
    if(!b){
        x = 1 ;
        y = 0 ;
        return a ;
    }else{
        int gcd = ex_gcd(b , a%b , x , y);
        int t = x ;
        x = y ;
        y = t - a/b*y;
        return gcd ;
    }
}

int EX_CRT(){
    for(int i = 2 ; i <= n ; i++){
        int d = ex_gcd(m[1] , m[i] , x , y);
        if((a[1] - a[i])%d){
            return -1 ;
        }
        int mo = m[i]/d;
        x = ((x * (a[1]-a[i])/d)%mo+mo)%mo ;
        int lcm = m[1] / __gcd(m[1] , m[i])  * m[i];
        a[1] = ((a[1]%lcm - m[1]%lcm * x % lcm ) % lcm + lcm) % lcm ; 
        m[1] = lcm;
    }
    return a[1];
}

素数筛

移步另一篇文章素数筛

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/nonames/p/12740041.html