PTA 1103 缘分数 C++实现

所谓缘分数是指这样一对正整数 a 和 b，其中 a 和它的小弟 a−1 的立方差正好是另一个整数 c 的平方，而 c 正好是 b 和它的小弟 b−1 的平方和。例如 8^3 − 7^3 = 169 = 13^2，而 13=3^2+2^2，于是 8 和 3 就是一对缘分数。

给定 a 所在的区间 [m,n]，是否存在缘分数？

输入格式：

输入给出区间的两个端点 0 < m < n ≤ 25000，其间以空格分隔。

输出格式：

按照 a 从小到大的顺序，每行输出一对缘分数，数字间以空格分隔。如果无解，则输出 No Solution。

输入样例 1：

8 200

输出样例 1：

8 3
105 10

输入样例 2：

9 100

输出样例 2：

No Solution

解题思路：

按题目要求模拟即可，其实最重要的点就在于 c 的处理，如何确定某数的平方就等于c呢？利用C++ 的 sqrt()平方根函数的特点就可以做到，即：(int)sqrt(c) * (int)sqrt(c) == c 如果此条件成立，那么 sqrt(c) 就一定是整数并且其平方一定等于 c。为什么这么说呢？下面我就来解释一下原理：

因为在 C++ 中，sqrt(c)得出的数是浮点数，比如若 c = 168 那么 sqrt(c) ≈ 12.961，那么(int)sqrt(c) = 12，于是168 ≠ 12^2；若 c = 169 那么 sqrt(c) = 13，那么(int)sqrt(c) = 13，于是169=13^2，这就是这个条件的合理性所在。

代码示例：

#include 
#include 
#include 

using namespace std;


int main()
{
	int begin, end;
	cin >> begin >> end;

	int key = 0; //是否有缘分数的标志，key=1就代表有缘分数
	for (int a = begin; a <= end; a++)
	{
		int b = -1; //a的待判断缘分数b b!=-1就代表找到了a的缘分数b
		int bro_a = a - 1;
		int c = a * a * a - bro_a * bro_a * bro_a;

		if ((int)sqrt(c) * (int)sqrt(c) == c)
		{
			for (int i = 1; i <= sqrt(c) / 2; i++)
			{
				if ((i * i) + (i + 1) * (i + 1) == sqrt(c))
				{
					b = i + 1; //a的缘分数b要取较大的数
					break;
				}
				
			}
		}

		if (b != -1)
		{
			cout << a << " " << b << endl;
			key = 1;
		}

	}

	if (key == 0)
	{
		cout << "No Solution" << endl;
	}

	return 0;

}

运行结果：