c++ - 计算乘法为完美平方的所有可能对的有效算法

Question

我有两个数字 N 和 M。我想有效地计算有多少对 a,b 使得 1<=a<=N 和 1<=b<=M 和 a*b 是一个完美的正方形。

我知道计算这个的明显的 N*M 算法。但我想要比这更好的东西。感谢您提前提供任何帮助。伪代码会更有帮助。

编辑：我认为它可以在更好的时间完成，可能是 O(m+n) 或类似的东西，但是直接从以前的对计算新的对，而不是遍历所有的 a 和 b。

Answer 1

我的方法是这样的：

1. 因为s是正方形和s <= N*M

   1. 对 进行素数分解s。

   2. 遍历这个素数分解的分区并检查哪些满足您的要求

遍历可能的分区可能有点棘手，但我很确定这是可能的最有效的方法。

另一方面，迭代平方数是微不足道的：

for(int i = 0, square = 0; /*whatever*/; square += 2*i++ + 1)

Answer 2

我会寻找一种使用素数分解的方法。获取 1 和 max(N,M) 之间的所有质数，我们称它们为 (p0, p1, ... pn)

那么任何数 a <= N 和 b <= M 都可以写成and ，对于 i 从 1 到 n，其中 ai 和 bi 可以是任何正整数或 0。

然后，任何乘积 a*b 都可以写为，并且在该写作中完美正方形的特征是所有 (ai+bi) 都需要是偶数（0 是偶数，为了记录）。

然后，您需要以某种方式迭代所有 (ai)，使得 a <= N，并且对于每组 (ai) 生成所有 (bi)，使得 b <= M 并且所有 (ai+bi) 是偶数。

不确定这是否接近有效，但应该可以正常工作。