不定方程正整数解的求解方法

吴昊羲（不在线）

2025-09-06 09:21:22

发布于：江苏

6阅读

0回复

0点赞

事先声明：作者是初中生，证明并不严谨，只能算说理，请多包涵。

在我们的数学生活与学习中，常常会看到这样一些小可爱：

3x + 5y = 36
4x - 20y = 68

这些方程被称为不定方程，题目常常会让你求正整数解。

作为一位初中生，我的解题思路将会异常简单：

就拿 3x + 5y = 36 举例，用 y 表示 x 可得 x = 12 - 5y / 3，由于 x 为正整数，因此 5y / 3 为正整数，又因为 y 是正整数，所以 y 是3的倍数，接下来把 y 列举出来：

y = 3 时，x = 7
y = 6 时，x = 2
y >= 9 时，x 为负数，不满足题意，舍去。

因此只有两组正整数解。

将这个方程一般化，即：

ax + by = c
此处 a、b、c 都是整数，且 a、b 都非0

我们可否找到一个通解呢？

阶段一

首先，我们先化简这个方程。由于这个方程有整数解，不妨设为 ( x', y' ) ，则 x'、y' 都为整数，为了让 a、b 最小，可以两边同除以 a、b 的最大公约数，显然 ax' + by' 是可以被 a、b 的最大公约数整除的，所以 c 也可以。

因此，我们可以在题目上多加一个条件：a、b 互质。

从刚刚解题过程中，可以发现，只要确定了一组解，所有解都可以推出来，那我们不妨设 ( x', y' ) 为一组已知解，显然 ax' + by' = c，此时 y' 若增加 k（ k 为整数），x' 必然减少 bk / a，由于 a、b 互质，k 必然为 a 的倍数，设 k = at，则 y' 每增加 at，x' 就减少 bt，这样，通解公式就出来了：

x = x' - bt
y = y' + at
此处 t 为整数

求正整数解时，只需舍去负数即可。

阶段二

那么这第一个 ( x', y' ) 如何求解呢？让我们回到原点，同样的方法，x = ( c - by ) / a，学过同余的反应应该很敏感，没错，c 与 by 模 a 同余，即 c % a = by % a，由阶段一可得 a、b 互质，因此可以两边同除以 b，可是 c / b 不一定是一个整数，因此我们可以在 c 上不停加 a，显然这不会影响等式结果，直到得到 c' 为 b 的倍数为止，c' / b % a = y % a，此时 y 的一个取值就出来了：

y = c' / b % a

自然，我们也能求出 x 的值，将这两个值作为阶段一中的 ( x', y' ) 就行了。

#include<bits/stdc++.h>
using namespace std;
int a,b,c,x,y;
int gcd(int a,int b){
	if(a<b) swap(a,b);
	if(b==0) return a;
	return gcd(b,a%b);
}
int main(){
	scanf("%d%d%d",&a,&b,&c);
	int n=gcd(a,b);
	if(c%n==0){
		a/=n;
		b/=n;
		c/=n;
		int t=c; 
		while(c%b!=0){
			c+=a;
		}
		y=c/b%a;
		if(y==0) y+=a;
		x=(t-b*y)/a;
		if(x<=0){
			cout<<"No Answer";
			return 0;
		}
		while(x>0){
			cout<<x<<" "<<y<<endl;
			y+=a;
			x-=b;
		}
	}else{
		cout<<"No Answer";
	}
	return 0;
}