关于方程

几何微粒子 · 2023-03-29 15:39:03 · 个人记录

我又来写博客了哈哈嗨

Chapter I 方程

方程的基本定义：含有未知数的等式

发展路线：

1

• 二元一次方程组 -> 多元一次方程组

• 一元二次方程 -> 一元高次方程

• 多项式方程 -> 超越方程

• 方程的形式越来越复杂

2

特定空间下求解

• e.g.一元二次方程

• 实数域 R 内求解 -> 判别式

• 复数域 C 内求解 -> 必有2根 x1,x2

不定方程：

在数论背景下，方程的解空间限制一般在整数集 Z 或者 有理数集 Q

这种方程称为丢番图方程。

这种方程大多数时候解不唯一，故又称不定方程。

Chapter II 二元一次不定方程

定义：

设 a,b,c 为非零整数，求关于 x,y 方程的整数解 ax+by=c

容易发现，方程左边 ax+by 必定为 d = \gcd(a,b) 的倍数。

因此立即得到该方程有整数解的一个必要条件是 d | c

而充分条件需要使用

如果裴蜀定理成立，则必要条件 d | c 立即升级为充分必要条件

设有 ax_0 + by_0 = \gcd(a,b) = d，则

为 ax + by = c 的一组解

Chapter III 扩展欧几里得算法 exgcd

相当于给了裴蜀定理一个构造性的证明

利用辗转相除法过程中得到的等式 r_{k-2} = r_{k-1} q_{k-1} + r_k

不断地将较小的 r_k 表示为 r_{k-1} 与 r_{k-2} 的线性组合

设原有 d = r_{k-1}x + r_k y

带入 r_{k-2} = r_{k-1} q{k-1} + r_k 得 d = r_{k-1}x + (r_{k-2} - r_{k-1} q_{k-1})y

整理得递推式 \begin{cases}x' = y \\ y' = x - q_{k-1} y\end{cases}

代码在这里的Chapter III

用这份代码实现exgcd具有以下特点

• 求解过程中 |x| \le |b| , |y| \le |a|，因此不会溢出，大喜

• 设 |a| \ge |b|，则求出的 x 满足 绝对值最小，即最小范数解

然后有了exgcd，就可以通过裴蜀定理求 ax+by=c 的全部解

• exgcd求 ax+by=d 的一组解 x_0,y_0

• 同时乘以 \dfrac{c}{d} 得到 ax+by=c 的一组解 x_1,y_1

• 得到全部解为 x = x_1 + \dfrac{b}{d} \times k , y = y_1 - \dfrac{a}{d} \times k

Chapter IV 一些方程

• 多元一次不定方程

先解决

所有的 g_2 的倍数都可以用 a_1 x_1 + a_2 x_2 表示，反之亦然。

原方程化为 g_2 t_2 + a_3 x_3 + \dots a_n x_n = b

继续这样，每次将两个式子合并为一个式子，最后得到 g_n t_n = b

然后解出 t_n 后再递归回去即可解出全部解。

代码：

#include<bits/stdc++.h>
using namespace std;

long long a[10];
long long n,b;
long long exgcd(long long a,long long b,long long &x,long long &y){
    long long d=a;
    if(b==0){
        x=1;
        y=0;
        return a;
    }else{
        d=exgcd(b,a%b,y,x);
        y-=a/b*x;
    }
    return d;
}
long long gcd(long long a,long long b){
    return b==0?a:gcd(b,a%b);
}
stack<long long>s;
void getjie(long long a,long long b,long long c,long long &x,long long &y){
    long long d=exgcd(a,b,x,y);
    x=x*(c/d);
    y=y*(c/d);
    long long k;
    if(x>0){
        k=min((x/b),-(y/a));
        x-=k*b,y+=k*a;
    }
    else{
        k=min(-(x/b),(y/a));
        x+=k*b,y-=k*a;
    }
}
long long g[10];
long long t[10];
int main(){
    scanf("%lld%lld",&n,&b);
    for(long long i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    long long x,y;
    long long last=0;
    for(long long i=1;i<=n;i++){
        if(i==1){
            g[i]=a[i];
        }else{
            g[i]=gcd(g[i-1],a[i]);
        }
    }
    long long xxx;
    for(long long i=n;i>=2;i--){
        if(i==n){
            getjie(g[i-1],a[i],b,x,y);
            s.push(y);
        }else if(i==2){
            xxx=x;
            getjie(g[i-1],a[i],g[i]*xxx,x,y);
            s.push(y);
            s.push(x);
        }else{
            xxx=x;
            getjie(g[i-1],a[i],g[i]*xxx,x,y);
            s.push(y);
        }
    }
    while(!s.empty()){
        printf("%d ",s.top());
        s.pop();
    }

return 0;
}

n b
a1 a2 a3 … an

因此，该方程有整数解的充分必要条件为

• 多元不定方程组

高斯消元，暂不讨论。

• 线性同余方程

含有未知数的同余式，且同余式中未知数次数为1，例如 ax\equiv b \pmod m

注意到同余式的其他等价写法，该同余方程与不定方程 ax - my = b 等价

因此可以用exgcd求解得 x = x_0 + m'k

通常也习惯将解也写为同余式 x \equiv x_0 \pmod {m'}

• 利用exgcd求逆元

解同余方程 ax \equiv 1 \pmod m 即可得到 a\mod m 的乘法逆元。

相比于费马小定理+矩阵快速幂的方法，优势是不要求 m 是质数

int getinv(int a,int m){
    int x,y;
    int d=exgcd(a,m,x,y);
    if(d!=1)//不互质 
        return -1;//当场逝世
    else
        return (x%m+m)%m;//求解得到的x，mod一下 
}

• 多元线性同余方程

解法和多元一次不定方程差不多。

• 线性同余方程组

求解 \begin{cases}x \equiv 2 \pmod 3 \\ x \equiv 3 \pmod 5 \\ x \equiv 2 \pmod 7\end{cases}

答案： x = 2 \times 70 + 3 \times 21 + 2 \times 15 = 233 \times 23 \pmod 105

70为5和7的倍数且%3同余1 21为3和7的倍数且%5同余1 15为3和5的倍数且%7同余1

因此易验得 2\times 70 + 3\times 21 + 2\times 15 同时满足三个同余式。

下面则是这个问题的结论：

Chapter IV 中国剩余定理

• China Recude Chinese Remainder Theorem，简称CRT

设 m_1,m_2,\dots ,m_n 两两互质，则关于 x 的线性同余方程组 \begin{cases}x\equiv b_1 \pmod {m_1} \\ x\equiv b_2 \pmod {m_2} \\ \dots\dots\dots\dots \\ x \equiv b_n \pmod {m_n}\end{cases} 对于任意正整数序列 b_1,b_2,\dots,b_n 均有正整数解且解集为 x\equiv x_0 \pmod {m_1,m_2,\dots ,m_n}

记作 m = \prod\limits_{i=1}^{n} m_i ， 且 M_i = \dfrac{m}{m_i}

1. 解 u_i\times M_i \equiv 1 \pmod m_i 得到关键参数 e_i = u_i \times M_i

2. 计算出解为 x\ \equiv e_1 b_1 + e_2 b_2 + \dots + e_n b_n \pmod m

中国剩余定理的本质为 \begin{cases}x \equiv 23 \pmod 3 \\ x \equiv 23 \pmod 5 \\ x \equiv 23 \pmod 7\end{cases} \Leftrightarrow x \equiv 23 \pmod {105}

既可以正向应用解方程，也可以逆向应用分解问题。也就是说，中国剩余定理存在逆定理

中国剩余定理及其构造性的解法要求模数两两互质

不互质时，可以逆用中国剩余定理，将其拆分为多个模 p^s 的方程，对于相同的 p 可以都合并为同一个方程，或者矛盾导致无解

e.g.

这个方法实在太麻烦了，所以我们让CRT学习gcd同志，让他稍微ex一下，变成

exCRT 拓展/扩展中国剩余定理

将同余式 \begin{cases}x \equiv b_1 \pmod {m_1} \\ x \equiv b_2 \pmod {m_2}\end{cases} 改写成等式 \begin{cases}x = b_1 + m_1 k_1 \\ x = b_2 + m_2 k_2\end{cases}，则 m_1 k_1 - m_2 k_2 = b_2 - b_1

是关于 k_1 和 k_2 的不定方程，有解的充要条件是 \gcd(m1,m2) \quad\!\!\! | \quad\!\!\!(b2-b1)

解除 k_1 = k_1' + \dfrac{m_2}{\gcd(m_1,m_2)}\times t 后代入得

注意到 \dfrac{m_1 m_2}{\gcd(m_1,m_2)} 为 [m_1,m_2]，也就是 lcm(m_1,m_2)

再次将解改为同余式

这样，我们做一次exgcd就可以把两个同余方程合并为一个

此外，拓展中国剩余定理分三种数据范围

• [m_1,m_2,m_3 \dots m_n] \le 10^{18}

• 保证有解，且解不超过 10^{18}

• 不保证有解，但有解的时候解不超过 10^{18}

Chapter V 高次方程

各种方程。

高次同余方程

如果 m 存在原根，设x = g^{x'},a=g^{a'} 则问题转换为 g^{x'n} \equiv g^{a'} \pmod m

也就是 x'n \equiv a\ \pmod {\varphi_m}

上述方程有解的条件显然为 \gcd(n, \varphi_m) | a'

且有解时解的数量为 \gcd(n,\varphi_m)

如果 x^n \equiv a \pmod m 中，m 不存在原根，设 m = p_1^{r_1} \times p_2^{r_2} \times \dots \times p_n^{r_n} ，用中国剩余定理拆分为 n 个方程，除了 2^s 外都有原根，则可以按照上述方法求解。

而 \mod 2^s 也有专门的求解方法。这里不再深究。

高次不定方程

<= 这几把就是个没通用解法的东西 =>

不再深究。

Chapter VI 方程的应用

应用

勾股数

不定方程 x^2 + y^2 = z^2 的一组整数解，x,y,z 成为一组勾股数。

当 \gcd(x,y,z) = 1 时，x,y,z 称作本原勾股数或 x^2 + y^2 = z^2 的本原解。

所有本原解可以唯一表示为 \begin{cases}x = m^2 - n^2 \\ y = 2mn \\ z = m^2+n^2 \end{cases} 其中 m>n 且 m,n 互质，还必定一奇一偶。

二平方和问题

解不定方程 x^2 + y^2 = C

当 C = 4\times k + 1 (k \in N^*) 且为质数时，该方程有唯一解（不考虑顺序与正负）

四平方和问题

解不定方程 a^2 + b^2 + c^2 + d^2 = n (n > 0)

这个东西看似结果应该很复杂，实际上很简洁：必定有正整数解

任意正整数可以分解为4个整数的平方之和

高斯整数和高斯质数

涉及虚数，不再深究

费马大定理

注意是大定理不是小定理

关于 x,y,z 的不定方程 x^n + y^n = z^n (n\ge 3) 无解

各位可以去尝试感性证明一下，提示：勾股定理

至于理性证明，各位可以长逝。