一元二次不定式求整数解

根据初等数论（二元一次不定方程）得出来的思路

一、定理储备：

这些笔记是来自B站老师无尽沙砾讲解后做下的笔记

然后我就开始想不能用程序来设计出求不定方程的整数解

首先我想着先把最大公约数函数写出来就是gcd，然后一系列的辗转相除需要保存q1,q2,..qn，

而且x0,y0与辗转相除的n有关于是我就用n_gcd函数来计算n,写着写着意识到Qn和Pn也是要在辗转相除的过程中求出来于是就让n_gcd返回一个数组来保存 n , Qn , Pn

最后在main函数中可以先用定理2进行判断 a b c 构成的不定方程是否有整数解

这是我自己的拙见，有改进的地方可以评论，吸取一下大佬们的建议

#include<iostream> #include<algorithm> #include<vector> const int MAXN = 100; using namespace std; int gcd(int a, int b) { return (a % b == 0) ? b : gcd(b, a % b); } vector<int> n_gcd(int a, int b) { int cnt = 0; vector<int> q(MAXN); vector<int> Q(MAXN); Q[0] = 0; Q[1] = 1; vector<int> P(MAXN); P[0] = 1; vector<int>ans(3); while (a % b != 0) { q[cnt + 1] = a / b; printf("%d ", q[cnt + 1]); int tmp = a; a = b; b = tmp % b; cnt++; } cout << endl; cout << "cnt:" << cnt; P[1] = q[1]; if (cnt >= 2) { for (int i = 2; i <= cnt; i++) { P[i] = q[i]*P[i - 1] + P[i - 2]; cout << "P:" << P[i] << endl; Q[i] = q[i]*Q[i - 1] + Q[i - 2]; cout << "Q:" << Q[i] << endl; } } ans[0] = cnt; ans[1] = Q[cnt]; ans[2] = P[cnt]; return ans; } int main() { int a, b, c; cin >> a >> b >> c; int gcd_ab = gcd(a, b); if (c % gcd_ab != 0) { printf("无正整数解\n"); return 0; } int a1 = a / gcd_ab; int b1 = b / gcd_ab; vector<int> nqp = n_gcd(a1, b1); cout << "nqp:" << nqp[0] << " " << nqp[1] << " " << nqp[2] << endl; //int x0 = ((-1) ^ (nqp[0]-1))*nqp[1]; //int y0 = ((-1) ^ (nqp[0])) * nqp[2]; int x0, y0; if (nqp[0] % 2 == 0) { x0 = -nqp[1]; y0 = nqp[2]; } else { x0 = nqp[1]; y0 = -nqp[2]; } cout << "x0: " << x0 << endl; cout << "y0: " << y0 << endl; int x1 = x0 * c / gcd_ab; int y1 = y0 * c / gcd_ab; printf("ax + by = c 的特解为：x0 = %d y0 = %d\n", x1, y1); printf("ax + by = c 的通解为:\nx = %d - %dt\ny = %d + %dt\nax + by = c 的正整数解为：\n", x1, b1, y1, a1); int cnt = 1; for (int i = -1e6; i <= 1e6; i++) { if (x1 - b1 * i > 0 && y1 + a1 * i > 0) { printf("x%d = %d,y%d = %d\n", cnt, x1 - b1 * i, cnt, y1 + a1 * i); } } return 0; }