已知一数与最大公约数，求数对中另一数的方法及实例

没问题，我来一步步给你拆解这个问题，结合你举的例子讲清楚解法～

核心原理 #

假设我们已知数对中的一个数是a，它们的最大公约数是d，要求另一个数n（满足题目给定的限制，比如这里n ≤ 50）。这里有个关键的转化：
我们可以把a和n都除以d，得到a' = a/d，n' = n/d。这时候**gcd(a', n')必须等于1**——因为我们已经把两个数的最大公约数d提取出来了，剩下的部分肯定是互质的。同时，n可以表示为d * n'，所以只要找到符合条件的n'，就能得到对应的n。

结合你的例子实操 #

你的例子是：找所有n ≤ 50且gcd(n, 50) = 5的n值。

1. 先计算a' = 50 / 5 = 10，同时n = 5 * n' ≤ 50，所以n' ≤ 10。
2. 接下来找1到10中，和10互质的数（也就是gcd为1的数）：1、3、7、9。
3. 把这些数乘以5，得到对应的n：5、15、35、45。

你可以验证一下：

• gcd(5,50)=5，符合；
• gcd(15,50)=5，符合；
• gcd(35,50)=5，符合；
• gcd(45,50)=5，符合。

通用步骤总结 #

不管题目里的已知数和限制是什么，都可以按这个流程来：

• 第一步：先确认d是a的约数（如果不是，那没有符合条件的n），然后计算a' = a/d；
• 第二步：根据n的限制（比如n ≤ max_n），算出n'的上限：max_n' = max_n / d；
• 第三步：找出所有1到max_n'中与a'互质的正整数n'；
• 第四步：每个符合条件的n'乘以d，得到的结果就是所有满足要求的n。

内容的提问来源于stack exchange，提问作者Nguyễn Tùng