2 つの数値 N と M があります。1<=a<=N および 1<=b<=M であり、a*b が完全な正方形であるような a,b のペアがいくつあるかを効率的に計算したいと考えています。
これを計算するための明白な N*M アルゴリズムを知っています。しかし、それよりも優れたものが欲しい。事前に助けてくれてありがとう。疑似コードがより役立ちます。
編集: O(m+n) などのより良い時間で実行できると思いますが、すべての a と b を反復するのではなく、前のペアから直接新しいペアを計算します。
素数分解を使用する方法を選択します。1 から max(N,M) までのすべての素数を取得し、それらを (p0, p1, ... pn) と呼びましょう。
次に、任意の数 a <= N および b <= M は、1 から n までの i に対して
andとして記述できます。ここで、ai と bi は任意の正の整数または 0 です。
次に、任意の積 a*b は として記述でき
、その記述における完全な正方形の特性化は、すべての (ai+bi) が偶数である必要があるということです (記録のために 0 は偶数です)。
次に、a <= N となるようにすべての (ai) を繰り返し処理し、(ai) のセットごとに b <= M となるようにすべての (bi) を生成し、すべての (ai+bi) が偶数になるようにする必要があります。
それがどこでも効率的かどうかはわかりませんが、問題なく動作するはずです。