二元一次方程の通项公式
_smart_stupid_
·
·
算法·理论
题目背景
某一天，小明在课本上看到了这样一个方程组：
\begin{cases}
ax+by=c\\
dx+ey=f
\end{cases}
小明不会解，求你来帮他。
解法
现在，我们来推导一元二次方程通项公式：
代入法
由 ax+by=c 可知，x=\frac{c-by}a。
代 x=\frac{c-by}a 入 dx+ey=f 得：
\frac{d(c-by)}a+ey=f
化简得到：
y=\frac{af-cd}{ae-bd}
代 y=\frac{af-cd}{ae-bd} 入 x=\frac{c-by}a 得：
x=\frac{c-b\frac{af-cd}{ae-bd}}a
$$
\begin{cases}
x=\frac{c-b\frac{af-cd}{ae-bd}}a
\\
y=\frac{af-cd}{ae-bd}
\end{cases}
$$
小明看到了你 ~~屎山一样~~ 的求解过程，不太确定，于是代入了 $a=2,b=3,c=8,d=3,e=2,f=7$ 求解，发现 $x=1,y=2$，正确。
## 消元法
将 $ax+by=c$ 乘上 $\frac da$ 得：
$$
dx+\frac{bd}ay=\frac{cd}a
$$
将 $dx+\frac{bd}a=\frac{cd}a$ 减去 $dx+ey=f$ 得：
$$
(\frac{bd}a-e)y=\frac{cd}a-f
$$
化简得到：
$$
y=\frac{cd-af}{bd-ae}
$$
代 $y=\frac{cd-af}{bd-ae}$ 入 $ax+by=c$ 得：
$$
ax+b\frac{cd-af}{bd-ae}=c
$$
化简得：
$$
x=\frac{c-b\frac{cd-af}{bd-ae}}a
$$
$\therefore$ 原方程式的解为：
$$
\begin{cases}
x=\frac{c-b\frac{cd-af}{bd-ae}}a
\\
y=\frac{cd-af}{bd-ae}
\end{cases}
$$
小明傻眼了：两个方法求出来的通项公式为什么不一样诶？
但是实际上我们用消元法求解时得到 $y=\frac{cd-af}{bd-ae}$ 时，将分数右边分子和分母同时乘上 $-1$，数值不变，再求解 $x$，就可以得到和代入法同样的结果。
# Code（使用 `double`）
```cpp
#include <bits/stdc++.h>
using namespace std;
double a, b, c, d, e, f;
int main() {
while (1) {
cout << "请输入 a, b, c, d, e, f 的值，以空格分隔\n";
cin >> a >> b >> c >> d >> e >> f;
cout << "x = " << (c - b * (c * d - a * f) / (b * d - a * e)) / a << '\n';
cout << "y = " << (c * d - a * f) / (b * d - a * e) << '\n';
return 0;
}
}
```
# Code（使用 `frac`）
```cpp
#include <bits/stdc++.h>
using namespace std;
struct frac{
long long x, y; // x / y
};
frac operator + (const frac &a, const frac &b) {
frac c;
c.y = a.y * b.y;
c.x = a.x * b.y + a.y * b.x;
long long temp = __gcd(c.x, c.y);
c.x /= temp, c.y /= temp;
if (c.y < 0) {
c.x *= -1, c.y *= -1;
}
return c;
}
frac operator - (const frac &a, const frac &b) {
frac c;
c.y = a.y * b.y;
c.x = a.x * b.y - a.y * b.x;
long long temp = __gcd(c.x, c.y);
c.x /= temp, c.y /= temp;
if (c.y < 0) {
c.x *= -1, c.y *= -1;
}
return c;
}
frac operator * (const frac &a, const frac &b) {
frac c;
c.y = a.y * b.y;
c.x = a.x * b.x;
long long temp = __gcd(c.x, c.y);
c.x /= temp, c.y /= temp;
if (c.y < 0) {
c.x *= -1, c.y *= -1;
}
return c;
}
frac operator / (const frac &a, const frac &b) {
frac c;
c.y = a.y * b.x;
c.x = a.x * b.y;
long long temp = __gcd(c.x, c.y);
c.x /= temp, c.y /= temp;
if (c.y < 0) {
c.x *= -1, c.y *= -1;
}
return c;
}
frac a, b, c, d, e, f;
int main() {
while (1) {
cout << "请输入 a, b, c, d, e, f 的分子和分母，以空格或换行分隔\n";
cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y
>> d.x >> d.y >> e.x >> e.y >> f.x >> f.y;
if (!a.y || !b.y || !c.y || !d.y || !e.y || !f.y) {
cout << "分母不可以为0！";
continue;
}
frac x = (c - b * (c * d - a * f) / (b * d - a * e)) / a;
frac y = (c * d - a * f) / (b * d - a * e);
cout << "x = " << x.x << " / " << x.y << '\n';
cout << "y = " << y.x << " / " << y.y << '\n';
}
return 0;
}
```