数年前、私は興味深いプログラミングの問題を発見しました。「1秒の制限時間で3つの正方形の合計に
分割する数を見つけること」。nn < 10^9
質問：与えられた制約でこの問題を解決する方法を知っている人はいますか？
私はそれが純粋に漸近的な時間計算量でO(n)のみよりも速くできると思いますか？いくつかの巧妙な数学のアプローチがありますか、それともコード最適化エンジニアリングの問題ですか？
https://oeis.org/A000164でいくつかの情報を見つけましたがO(n)、FORMULAセクションに-algoがあり
（n-k^2計算のために各数値のすべての除数を見つける必要があるためe(n-k^2)）O(n)、MAPLEセクションに-algoがあります。
はい。まず、数n - z^2を素数に因数分解し、素数をガウス共役に分解し、さまざまな式を見つけて展開および単純化してa + bi、を取得します。これを上げることができますa^2 + b^2。奇数の力を持つn - z^2素数を含む候補を除外することができ4k + 3ます。
これは、数値をガウス整数共役として表現することに基づいています。(a + bi)*(a - bi) = a^2 + b^2。https://mathoverflow.net/questions/29644/enumerating-ways-to-decompose-an-integer-into-the-sum-of-two-squaresおよびhttps://stackoverflow.com/a/54839035/2034787を参照してください
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加