数学基础——同余

线性同余方程

• 给定(a,b,c),求一个整数(x)满足(axequiv c(mod;b)), 或给出无解

• 因为有(b|ax-c),设(ax-c = -y*b),则方程改写为(ax+by = c),就可以用(exgcd)求解

• 注意,根据裴蜀定理,(ax+by = c)有解当且仅当
  ((a,b)|c),(即(c\%(a,b) == 0))

代码如下

#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;

ll exgcd(ll a,ll b,ll &x,ll &y) {
	if(b == 0) {
		x = 1; y = 0; return a;
	}
	ll d = exgcd(b,a%b,x,y);//引用是相当于返回了(b,a%b)的一组解x0,y0 
	ll t = x; x = y; y = t-(a/b)*y;//通过变换x0,y0可得(a,b)的一组解x,y 
	return d;
}

int main() {
	ll a,b,c = 1,x,y;
	cin >> a >> b;
	ll g_ab = exgcd(a,b,x,y); 
	if(c%g_ab) {
		cout << -1; return 0;
		//如果无解 
		//此题保证有解,即保证 gcd(a,b)|c 即保证gcd(a,b) = 1
	}
	x = x/g_ab*c;
	cout << (x%b+b)%b;//将求得的x调整到范围内 
	return 0;
}

乘法逆元

• 作用

  将模意义下的除法转化为乘法

• 求法

  • 求(a)关于(mod;p)的逆元

    • (a,p)互质,(p)为质数

      (a^{p-1} equiv 1(mod;p))(费马小定理)

      所以有(a*a^{p-2} equiv 1 (mod;p)),即(a^{p-2})为(a)在(mod;p)意义下的逆元

      利用快速幂即可求解,时间复杂度(O(log(p)))

    • 只满足(a,p)互质

      求解线性同余方程(a*x equiv 1 (mod;p))

      利用(exgcd)即可求解,时间复杂度(O(log(p)))(近似)

  • 线性递推求逆元

    求([1,n])关于(mod;M)的逆元

    有递推式

    [inv[i] = (M-left lfloor M/i ight floor)*inv[M\%i]\%M ]

    推导如下

    (M = t*i+r,t = left lfloor M/i ight floor,r = M\%i)

    有(t*i+r equiv 0 (mod;M)),即(r equiv -t*i(mod;M))

    两边同除(i*r)(即同乘(inv[i]*inv[r]))

    得(inv[i] equiv -t*inv[r](mod;M))

    代换(t,r)得(inv[i] equiv -left lfloor M/i ight floor*inv[M\%i](mod;M))

    则(inv[i])的通解为(inv[i] = -left lfloor M/i ight floor*inv[M\%i] + k*M)

    为了方便,写成上述的递推式

    [inv[i] = (M-left lfloor M/i ight floor)*inv[M\%i]\%M ]

    时间复杂度(O(n))

    inv[1] = 1;
    for(int i = 2;i < M; ++i) {//if n < M ,i <= n即可
           inv[i] = (M-M/i)*inv[M%i]%M;
    }
    

  • (O(n))求阶乘逆元(多用于配合求组合数)

    可以用上面的递推先求出([1,n])的逆元,然后求出阶乘逆元

    但我们有更为优秀的做法,直接求阶乘逆元

    令(inv[i])表示(i!)关于(mod;M)的逆元

    有$$inv[i+1] * (i+1) Leftrightarrow frac{1}{(i+1)!}*(i+1) Leftrightarrow frac{1}{i!} Leftrightarrow inv[i]$$

    即$$inv[i] = inv[i+1]*(i+1)%M$$

    先求出(n!)的逆元,然后逆推

    时间复杂度(O(n))(准确是近似(O(n+log(p))))

(crt)

• 基础应用 : 求解模数互质的线性同余方程组

[(S)egin{cases} x equiv a_1(mod ;m_1)\ x equiv a_2(mod ;m_2)\ x equiv a_3(mod ;m_3)\ ......\ x equiv a_n(mod ;m_n) end{cases} ]

• 解为

[x = sum_{i = 1}^n a_iM_it_i + kM ]

• 其中(M = prod_{i = 1}^n m_i,M_i = M/m_i),
  (t_i)是(M_i)在(mod;m_i)意义下的逆元,即(M_it_i equiv 1(mod;m_i))

• 带入原方程组即可验证正确性

• 代码如下

int n,a[N],m[N];

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

ll crt(ll a[],ll m[],int n) {
	ll res = 0,M = 1;
	for(int i = 1;i <= n; ++i) M *= m[i];
	for(int i = 1;i <= n; ++i) {
		ll M_i = M/m[i],t,y;
		exgcd(M_i,m[i],t,y);
		res = (res+(a[i]*M_i*t)%M)%M;
	}
	return (res+M)%M;
}

(excrt)

• 基础应用

  求解模数不互质的线性同余方程组

• 求法

  假设已经求得前(i-1)个方程的一个解(x_0),则前(i-1)个方程的通解为

  [X = x_0+k*M_{i-1} ]

  其中(M_{i-1})为([m_1,m_2,m_3...m_{i-1}])

  那么对于第(i)个方程,即求一个(t),

  使得(X equiv a_i(mod;m_i))成立,即求解线性同余方程

  [M_{i-1}*t equiv a_i-x_0(mod;m_i) ]

  利用(exgcd)求得(如果无解则此方程组无解)前(i)个方程的一个解为(x_0{'} = x_0+t*M_{i-1}),则前(i)个方程的通解为

  [X{'} = x_0{'}+k*[M_{i-1},m_i] ]

  所以做(n-1)次(exgcd)即可求得解

• 注意

  由于出题人的毒瘤,经常会爆(long;long),所以可采用慢速乘对一次乘法多次取模,使用慢速乘的时候要尤其注意(a*b;mod;p)中(b)必须为正(否则会死循环)

• 代码如下

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

ll mul(ll a,ll b,ll p) {
    ll res = 0;
    b = (b%p+p)%p;
    for(; b;b >>= 1) {
        if(b&1) res = (res+a)%p;
        a = (a<<1)%p;
    }
    return res;
}

ll excrt(ll a[],ll m[],int n) {
    ll X = a[1],M = m[1],t,y;
    for(int i = 2;i <= n; ++i) {
        ll c = ((a[i]-X)%m[i]+m[i])%m[i];
        ll g = exgcd(M,m[i],t,y),mi = m[i]/g;
        if(c%g) return -1;
        t = mul(t,c/g,mi);
        X += M*t;
        M *= mi;
        X = (X%M+M)%M;
    }
    return (X%M+M)%M;
}

• (crt)和(excrt)都需注意的一点

  题目中的(a[N],m[N])数组有时是反着给的,要看清楚

(BSGS)

• 咕咕咕(太累了,有时间再学吧)