PTA 1104 天长地久 (20 分) C++实现 详细解答

PTA 1104 天长地久 (20 分) C++实现 详细解答,第1张

PTA 1104 天长地久 (20 分) C++实现 详细解答

天长地久数”是指一个 K 位正整数 A,其满足条件为:A 的各位数字之和为 m,A+1 的各位数字之和为 n,且 m 与 n 的最大公约数是一个大于 2 的素数。本题就请你找出这些天长地久数。

输入格式:

输入在第一行给出正整数 N(≤5),随后 N 行,每行给出一对 K(3 输出格式:

对每一对输入的 K 和 m,首先在一行中输出 Case X,其中 X 是输出的编号(从 1 开始);然后一行输出对应的 n 和 A,数字间以空格分隔。如果解不唯一,则每组解占一行,按 n 的递增序输出;若仍不唯一,则按 A 的递增序输出。若解不存在,则在一行中输出 No Solution。

输入样例:
2
6 45
7 80
输出样例:
Case 1
10 189999
10 279999
10 369999
10 459999
10 549999
10 639999
10 729999
10 819999
10 909999
Case 2
No Solution
解题思路:

暴力枚举法会超时,只能运用剪枝法来减少时间复杂度。

我们可以每枚举一位数就用sum去累加这个数,假如已经枚举了三位数,还剩下三位数没有枚举,如果已经枚举了三位数的和再加上3个9都还是小于k的话,就没必要继续枚举下去了,这就是剪枝法的作用。

代码示例:
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

//得到最大公约数
int gcd(int a, int b)
{
	if (a < b)
	{
		int temp = a;
		a = b;
		b = temp;
	}

	while (a % b != 0)
	{
		int temp = a % b;
		a = b;
		b = temp;
	}
	return b;

}

//判断某数是否是素数
bool isPrime(int x)
{
	if (x <= 1)
	{
		return false;
	}

	for (int i = 2; i <= sqrt(x); i++)
	{
		if (x % i == 0)
		{
			return false;
		}
	}
	return true;
}


bool flag; //是否有解的标志 若flag==true则代表有解

unordered_set res; //无序set容器res 存所有满足题目条件的n

//有序set容器ans pair的作用是可以按照第一个int升序,若相等则按第二个int升序排序
set> ans;

//cnt是用于记录枚举了第几位数了 k是需要枚举到的位数 m是需要达到的各位数之和 sum是各位数之和
void dfs(int cnt, int k, int m, int sum, int A)
{
	if (cnt > k) return;

	if (sum + (k - cnt) * 9 < m) return; //剪枝作用

	if (cnt == k)
	{
		if (sum == m)
		{
			int B = A + 1;
			int n = 0;
			while (B != 0)
			{
				n += B % 10;
				B /= 10;
			}

			if (res.count(n)) //此时如果res中有n这个数,那么就代表有解了
			{
				flag = true;
				ans.insert({ n,A }); //将符合条件的n和A插入到ans中
			}

		}
		return;
	}

	for (int i = 0; i <= 9; i++)
	{
		if (cnt == 0 && i == 0) continue; //首位不能是0 比如不能是01

		dfs(cnt + 1, k, m, sum + i, A * 10 + i); //每枚举一位数i,A就要乘10加i

	}


}

int main()
{
	int N;
	cin >> N;

	for (int i = 1; i <= N; i++)
	{
		int k, m;
		cin >> k >> m;

		printf("Case %dn", i);
		
		flag = false;
		res.clear();
		ans.clear();

		for (int n = 1; n <= 90; n++)
		{
			int temp = gcd(n, m);
			if (temp > 2 && isPrime(temp))
			{
				res.insert(n);
			}
		}

		dfs(0, k, m, 0, 0);

		if (flag == false)
		{
			puts("No Solution");
		}
		else
		{
			for (const auto& index : ans)
			{
				cout << index.first << " " << index.second << endl;
			}
		}
	}

	return 0;

}
运行结果:

 

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5710862.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存