一元二次不定式求整数解

根据初等数论二元一次不定方程得出来的思路一、定理储备这些笔记是来自B站老师无尽沙砾讲解后做下的笔记然后我就开始想不能用程序来设计出求不定方程的整数解首先我想着先把最大公约数函数写出来就是gcd然后一系列的辗转相除需要保存q1,q2,..qn而且x0,y0与辗转相除的n有关于是我就用n_gcd函数来计算n,写着写着意识到Qn和Pn也是要在辗转相除的过程中求出来于是就让n_gcd返回一个数组来保存 n , Qn , Pn最后在main函数中可以先用定理2进行判断 a b c 构成的不定方程是否有整数解这是我自己的拙见有改进的地方可以评论吸取一下大佬们的建议#includeiostream #includealgorithm #includevector const int MAXN 100; using namespace std; int gcd(int a, int b) { return (a % b 0) ? b : gcd(b, a % b); } vectorint n_gcd(int a, int b) { int cnt 0; vectorint q(MAXN); vectorint Q(MAXN); Q[0] 0; Q[1] 1; vectorint P(MAXN); P[0] 1; vectorintans(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; vectorint 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; }