不定方程

csuzhucong

已于 2025-05-04 00:30:22 修改

阅读量2.1k

点赞数

分类专栏：待更新文章标签：数论

于 2021-04-14 20:25:23 首次发布

本文链接：https://blog.csdn.net/nameofcsdn/article/details/115708334

版权

待更新专栏收录该内容

3 篇文章

订阅专栏

本文探讨了多元一次不定方程的暴力枚举解法，佩尔方程的理论及其应用，包括如何求解x^2-61*y^2=1的最小解，并介绍了其他相关数学问题，如勾股数、幂和方程的性质。此外，还涉及编程挑战，如最小好进制的寻找和解决实际数学题目的实例。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

一，多元一次不定方程

CodeForces 681B Economy Game

UVA 10673 Play with Floor and Ceil

方程abc=a!+b!+c!

方程abc=a!+b!+c!的拓展

51Nod 2167 ProjectEuler 34

理工科硕士爸爸解一年级数学题急出汗

一，多元一次不定方程

CodeForces 681B Economy Game

题目：

Description

Kolya is developing an economy simulator game. His most favourite part of the development process is in-game testing. Once he was entertained by the testing so much, that he found out his game-coin score become equal to 0.

Kolya remembers that at the beginning of the game his game-coin score was equal to n and that he have bought only some houses (for 1 234 567 game-coins each), cars (for 123 456 game-coins each) and computers (for 1 234 game-coins each).

Kolya is now interested, whether he could have spent all of his initial n game-coins buying only houses, cars and computers or there is a bug in the game. Formally, is there a triple of non-negative integers a, b and c such that a × 1 234 567 + b × 123 456 + c × 1 234 = n?

Please help Kolya answer this question.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 109) — Kolya's initial game-coin score.

Output

Print "YES" (without quotes) if it's possible that Kolya spent all of his initial n coins buying only houses, cars and computers. Otherwise print "NO" (without quotes).

Sample Input

Input
1359257
Output
YES
Input
17851817
Output
NO

这个题目就是暴力枚举而且，当然了，是二重循环而不是三重循环。

唯一的技巧就是，在内存循环之前，先判断了n的奇偶性，因为（56,1234）=2

加了这一句，就从30ms变成了15ms

代码：

#include<iostream>
using namespace std;
 
 
int main()
{
	int n;
	while (cin>>n)
	{
		bool flag = false;
		for (int a = 0; n>=0; a++)
		{			
			if (n % 2==0)
			{
				for (int b = 0; b <= n / 123456; b++)
				{
					if ((n - 56 * b) % 1234 == 0)
					{
						flag = true;
						break;
					}
				}
			}			
			if (flag)break;
			n -= 1234567;
		}
		if (flag)cout << "YES";
		else cout << "NO";
		cout << endl;
	}
	return 0;
}

二，佩尔方程（I型）

1，佩尔方程（I型）

2，佩尔方程定理

（1）如果d是正整数，不是完全平方数，那么一定有解，

如果 $(x_1,y_1)$ 是最小解，那么所有的解 $(x_k,y_k)$ 都可以用最小解的幂求出：

$x_k+y_k\sqrt{d}=(x_1+y_1\sqrt{d})^k$

（2）如果d<=0，或者d是完全平方数，那么一定有x=0或y=0

3，佩尔方程 x^2-61*y^2=1

下面我将编程求解它的最小解

如果直接枚举x和y的话，大约需要10秒

代码：

#include<iostream>
using namespace std;

int main()
{
	long long x = 2, y = 0, flag = 3;		//flag=x*x-61*y*y-1
	while (flag)
	{
		if (flag > 0)
		{
			flag -= 61 * (2 * y + 1);
			y++;
		}
		else
		{
			flag += 2 * x + 1;
			x++;
		}
	}
	cout << x << "  " << y << "  " << x*x;
	system("pause>nul");
	return 0;
}

如果先数学求解的话，自然会快一些。

首先，x必定是奇数，y必定是偶数

设x=s*2+1,y=t*2

那么s(s+1)=61t*2

分解：有2种情况

第一种，s=61*a^2,s+1=b^2,那么b^2-61*a^2=1，与x,y是最小解矛盾。

第二种，s=a^2,s+1=61*b^2,那么a^2-61*b^2=-1，化成这种佩尔方程了。

如果这个方程有解的话，原方程也有解，而且这个方程的解比原方程的解小得多。

2个方程是几乎差不多的，代码只需要略略改改就可以了。

代码：

#include<iostream>
using namespace std;

int main()
{
	long long x = 2, y = 0, flag = 5;
	while (flag)
	{
		if (flag > 0)
		{
			flag -= 61 * (2 * y + 1);
			y++;
		}
		else
		{
			flag += 2 * x + 1;
			x++;
		}
	}
	cout << x*x * 2 + 1;
	system("pause>nul");
	return 0;
}

这个不需要1秒就可以算完。

最后，附上PDF的截图

三，佩尔方程（II型）

目前没有有效判断是否有解的方法。

如果 $(x_1,y_1)$ 是最小解，那么所有的解 $(x_k,y_k)$ 都可以用最小解的幂求出：

$x_k+y_k\sqrt{d}=(x_1+y_1\sqrt{d})^{2k-1}$

四，勾股数、幂和方程

1，勾股数

（1）勾股数的通项公式：2uvd、(u^2-v^2)d、(u^2+v^2)d，其中(u,v)=1且u,v一奇一偶
（2）若x^2、y^2、z^2成等差数列，则x,y,z都是奇数，进一步可推出通项公式：
$x=\frac d2(u^2-2uv-v^2),\,y=\frac d2(u^2+v^2),\,z=\frac d2(u^2+2uv-v^2)$
（3）4个平方和不可能成等差数列

2，x^4+y^4=z^2（无穷递降法）

证明 $x^4+y^4=z^2$ 只有xy=0的解。

假设存在其他解，那么最小解可以表示成 $x^2=2uv, y^2=u^2-v^2, z=u^2+v^2,(u,v)=1$ ，其中u是奇数，v是偶数

根据 $x^2=2uv$ 可得， $u=s^2, v=2t^2$

根据 $y^2=u^2-v^2$ 可得， $y=a^2-b^2,v=2ab,u=a^2+b^2,(a,b)=1$

所以 $t^2=ab,s^2=a^2+b^2$

所以 $a=c^2,b=d^2,s^2=c^4+d^4$

这样就得到了更小的解，矛盾！

3，其他幂和方程

（1）x,y,z两两互素， $2|x,n>1$ ，则 $y^n=z^2-x^2$ 的解为

$z=\frac{(a+b)^n+(a-b)^n}{2},x=\frac{(a+b)^n-(a-b)^n}{2},y=a^2-b^2$ ，

其中a>b>0，(a,b)=1，2|ab

（2）

4，力扣 483. 最小好进制

以字符串的形式给出 n , 以字符串的形式返回 n 的最小 好进制 。

如果 n 的 k(k>=2) 进制数的所有数位全为1，则称 k(k>=2) 是 n 的一个 好进制 。

示例 1：

输入：n = "13"
输出："3"
解释：13 的 3 进制是 111。

示例 2：

输入：n = "4681"
输出："8"
解释：4681 的 8 进制是 11111。

示例 3：

输入：n = "1000000000000000000"
输出："999999999999999999"
解释：1000000000000000000 的 999999999999999999 进制是 11。

提示：

n 的取值范围是 [3, 1018]
n 没有前导 0

class Solution {
public:
	long long smallestGoodBase(long long n) { // solve k^m = n*k - n +1
		//m>3
		for (long long k = 2; k*k*k < n; k++) {
			if (n%k != 1)continue;
			long long km = n - (n - 1) / k;
			while (km%k == 0)km /= k;
			if (km == 1)return k;
		}
		//m=3
		long long k = sqrt(n - 3.0 / 4);
		if (k>1 && k*k + k + 1 == n)return k;
		//m=2
		return n - 1;
	}
	string smallestGoodBase(string n) {
		long long nn = StrToInt(n.data(), 10);
		long long ans = smallestGoodBase(nn);
		char *s = new char[20];
		int len = IntToStr(ans, 10, s);
		return string(s);
	}
};

五，环形跑道运动问题

0，背景思路

如果涉及到多个对象的运动问题，只需要先把AB的所有重合时间算出来，再把AC的所有重合时间算出来，再把AD的所有重合时间算出来......

所以下面的各种场景，我们都要把所有重合时间算出来

1，连续空间，连续时间，追及问题

问题：跑道长为L，A每秒运动x，B每秒运动y，x>y，追及运动，A到B的距离是c，求所有重合时间。

不定方程：xt-yt=c+nL，其中n>=0，求实数t

分析：无论给的x y c L是多少，一定有无穷多解

2，连续空间，连续时间，相遇问题

问题：跑道长为L，A每秒运动x，B每秒运动y，相向运动，A到B的距离是c，求所有重合时间。

不定方程：xt+yt=c+nL，其中n>=0，求实数t

分析：无论给的x y c L是多少，一定有无穷多解

3，连续空间，离散时间，同时运动，追及问题

PS：对于一些回合制游戏，或者考虑兔子这样一蹦一蹦的，可以用离散时间描述。

问题：跑道长为L，每回合AB同时运动，A运动x，B运动y，x>y，追及运动，A到B的距离是c，求所有重合时间。

不定方程：xm-ym=c+nL，其中n>=0，求整数m

分析：对于不同的x y c L，m可能有唯一解，可能有无穷多解，也可能无解

4，连续空间，离散时间，同时运动，相遇问题

5，连续空间，离散时间，依次运动，追及问题

6，连续空间，离散时间，依次运动，相遇问题

7，离散空间

六，其他不定方程

UVA 10673 Play with Floor and Ceil

题目：

我看网上基本上都是用欧几里得做的。。。

设s=x/k，那么，x=s*k+t，0≤t<k

那么方程化为s*k+t=p*k+q*(k+(t>0))

如果t=0,那么s=p+q，取p=s，q=0

如果t>0，那么s*k+t=(p+q)*k+q,取p=s-t,q=t

所以上面2种情况是一样的。

代码：

#include<iostream>
#include<stdio.h>
using namespace std;
 
int main()
{
	int n, x, k;
	scanf("%d", &n);
	while (n--)
	{
		scanf("%d%d", &x, &k);
		printf("%d %d\n", k - x%k, x%k);
	}
	return 0;
}

方程abc=a!+b!+c!

题目：求方程abc=a!+b!+c!的所有解

其中abc是三位数，三位分别为a、b、c

只需要一个求阶乘的函数即可。

代码：

#include<iostream>
using namespace std;

int fac[]={1,1,2,6,24,120,720,5040,40320,362880};

int main()
{
	for (int a = 1; a < 10; a++)for (int b = 0; b < 10; b++)for (int c = 0; c < 10; c++)
	if (a * 100 + b * 10 + c == fac[a] + fac[b] + fac[c])cout << a << b << c << endl;
	cout << "end";
	system("pause>nul");
	return 0;
}

求出145是唯一解

方程abc=a!+b!+c!的拓展

对于任意正整数n，各位数字阶乘后等于n本身，这样的n有多少个？

首先可以确定n的范围，100<=n<=2999999

然后可以枚举出结果：

145 40585 是仅有的2个解

51Nod 2167 ProjectEuler 34

145 是一个古怪的数字，因为 1! + 4! + 5! = 1 + 24 + 120 = 145。

输入n，求所有小于等于n且各位阶乘和等于本身的数字之和。

注意，1! = 1 和 2! = 2 并不算古怪的数字。

Input

输入第一行组数T，接下来T行，每行一个整数n。 (1 <= T <= 5) (1 <= n <= 100000000)

Output

对于每组数据，输出一个数，表示所有小于等于n，各位阶乘和等于本身的数字之和。

Sample Input

1
145

Sample Output

#include<iostream>
using namespace std;


int main()
{
	int t,n;
	cin>>t;
	while(t--)
    {
	    cin>>n;
	    cout<<(n>=145)*145+(n>=40585)*40585<<endl;
    }
	return 0;
}