c++ - 如何找到满足 GCD(a,b) = x 的 a,b

转载 作者：行者123 更新时间：2023-11-28 03:31:57 30 4

我正在尝试解决 the SPOJ problem PGCD , 它询问最大公约数表中出现了多少个素数。

我想到的第一个想法是先通过筛分生成素数。

然后，对于每个素数 p，查看有多少对(a，b)，其中 a和b都小于给定的边界，满足GCD(a,b)=p。

比如小于(20, 20)的对有多少对满足GCD(a,b)=7？

当然，如上所述，a 和b 是有界的。

那么有没有可能逆转GCD呢？还是这个方案完全无效？

最佳答案

显然 GCD 函数是不可逆的/可逆的，因为，例如，

• GCD(10,15) == 5
• GCD(5, 15) == 5

因此，如果给你 5 并尝试猜测输入，那是不可能的。

我可能在这里遗漏了一些东西，因为我不明白你在说什么边界，但我认为你有责任更好地解释这个问题。你到底有什么信息，你想计算什么信息？示例输入和输出将非常有用。此外，校对和拼写检查。

关于c++ - 如何找到满足 GCD(a,b) = x 的 a,b<N 对数？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12287548/

30 4 0