我正在尝试解决the SPOJ problem PGCD，该问题询问最大公约数表中出现了多少个素数。
我想到的第一个想法是先通过筛分产生素数。
然后，对于每个素数p，查看有多少对（a，b）满足GCD(a,b)=p，其中a和b小于给定范围。
例如，小于（20，20）的几对满足GCD（a，b）= 7？
当然，如上所述，a和b是有界的。
那么可以逆转GCD吗？还是这种解决方案完全无效？
最佳答案
显然，GCD功能不可逆/不可逆，例如，
GCD（10,15）== 5
GCD（5，15）== 5
因此，如果给定5并尝试猜测输入，则不可能。
我在这里可能会遗漏一些东西，因为我不明白您在说什么边界，但是我认为这是您更好地解释问题的责任。确切地说，您拥有什么信息，以及您想计算什么信息？示例输入和输出将非常有用。另外，校对和拼写检查。
关于c++ - 我如何找到对数a，b <N使得GCD(a，b)= x？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/12287548/